一个有关最短时间的计算的算法的问题,谢谢

Problem Description
在每年的校赛里,所有进入决赛的同学都会获得一件很漂亮的t-shirt。但是每当我们的工作人员把上百件的衣服从商店运回到赛场的时候,却是非常累的!所以现在他们想要寻找最短的从商店到赛场的路线,你可以帮助他们吗?

Input
输入包括多组数据。每组数据第一行是两个整数N、M(N<=100,M<=10000),N表示成都的大街上有几个路口,标号为1的路口是商店所在地,标号为N的路口是赛场所在地,M则表示在成都有几条路。N=M=0表示输入结束。接下来M行,每行包括3个整数A,B,C(1<=A,B<=N,1<=C<=1000),表示在路口A与路口B之间有一条路,我们的工作人员需要C分钟的时间走过这条路。
输入保证至少存在1条商店到赛场的路线。

Output
对于每组输入,输出一行,表示工作人员从商店走到赛场的最短时间

Sample Input
2 1
1 2 3
3 3
1 2 5
2 3 5
3 1 2
0 0

Sample Output
3
2

0
扫码支付0.1元 ×
其他相关推荐
TCP协议中可能涉及的计算题
此篇文章主要是为了解决以TCP协议为背景的一些计算题。概念题总结在TCP概览中。 例1:source:天勤:chapter5 分析:具有相同编号的TPDU不应该同时在网络中传输,必须保证,当序列号循环回来重复使用的时候,具有相同序列号的TPDU已经从网络中消失。现在存活时间是30s。那么在30s的时间内发送方发送的TPDU的数目不能多于256个。 所以最大数据传输速率:256*128*8...
城市之间的最短总距离(最小生成树算法)
求解城市之间的最短总距离是一个非常实际的问题,其大意如下: 某地区由n个城市,如何选择一条路线使各个城市之间的总距离最短? 1.最短总距离算法 先来分析一下上述问题。某个地区的n个城市构成一个交通图,可以使用图结构来描述此问题,其对应关系如下: 每个城市代表图中的一个顶点。 两个顶点间的边即两个城市之间的路径,边的权值代表了城市间的距离。 这样,求解各个城市之间的最短总距离问题...
过桥时间最短问题
【问题描述】       n个人要晚上过桥,在任何时候最多两个人一组过桥,每组要有一只手电筒。在这n个人中只有一个手电筒能用,因此要安排以某种往返的方式来返还手电筒,使更多的人可以过桥。       每个人的过桥速度不同,每组的速度由过桥最慢的人所用的时间决定,约定n 【输入】      输入的第一行给出n,接下来的n行给出每个人的过桥时间,不会超过1000人,且没有人的过桥时间会超过10
四人过河用时最短的编程实现
某夜,有个团伙要过桥,该桥每次只能通行2个人,只有一个手电筒,过桥必须持有手电筒。这些人单独过桥的时间从小到大分别为t1、t2、t3、t4、t5 ………请写程序计算出这伙人过桥需要的最短时间。(提示:假设是四人,如果t1=1,t2=2,t3=5,t4=10,最短用时为17)昨天公司领导出了上面逻辑题,看着挺有意思,自己初略思索了下,琢磨最短用时应该19才是,后面某一同事提了个方案: t1t2一起过...
增广路求最大流:EK算法详解
算法简介:EK算法,全称Edmonds-Karp算法。我个人认为学习一个新算法时有必要去记一下算法的英文全称,可以在同学们面前装逼(但是别装过头了,挨打了不是我的责任......)!最坏情况下的时间复杂度O(n*m^2)。我这个版本用BFS找增广路(当然也可以用DFS,但是时间复杂度......),存图用邻接表。不会BFS和邻接表的同学请......------------------------...
最短加法链问题,POJ2248,BFS,搜索
该题也是算法导论的结课作业,看了一下
Java(顾客最短等待时间)
题目如下: 设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti(1&amp;lt;i&amp;lt;n),共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使得平均等待时间达到最小?平均等待时间是n个顾客等待时间的总和除以n。 代码如下: package TXSF; import java.util.Scanner; public class ZY { public static vo...
通过一个实例学会时间复杂度的计算
时间复杂度的定义      一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n))为算法的渐进时间复杂度(O是数量级的符号 ),简称时间复杂度。 根据定义,可以归纳出基本的计算步骤  1.
每日一练——轮询调度算法和短作业优先调度算法的平均等待时间
今天做亚信的笔试题遇到的轮询调度算法,和春招做的百度笔试题短作业优先调度算法很相似,但是难度要UPUP。做题的过程中,因为没有正确地处理迭代器失效的问题浪费了好多时间(>﹏ 轮询调度算法 如果一个系统可以在单个CPU上运行多个并发作业,那么就该系统而言,“调度”是指:系统选择运行哪些任务,何时运行,何时中断以及以何种方式运行或中断。轮询调度规则是指:每个作业运行时间固定,该作业结束后,切换
图论算法(4) --- TSP旅行商问题 求最短回路(acm)
对于TSP旅行商问题,我们做的最多的也就是求最短回路了,那么对于一个数据量适中的图来说,一般的dfs方法即可求解,在这里,我应用dfs的思想来实现此问题,而关键之处在于对矩阵的改进,这样的操作可以使得应用搜索思想求TSP问题时,效率有显著的提高。 对于矩阵的改进,我们对矩阵的处理是,每一行减去所在行的最小值,每一列减去所在列的最小值,并把这些最小值加到结果sum中,这样的操作是将矩阵稀疏
17分钟过桥,过桥最短时间问题
智力测试题:在漆黑的夜里,四位旅行者来到了一座狭窄而且没有护栏的桥边。如果不借助手电筒的话,大家是无论如何也不敢过桥去的。不幸的是,四个人一共只带了一只手电筒,而桥窄得只够让两个人同时通过。如果各自单独过桥的话,四人所需要的时间分别是1,2,5,8分钟;而如果两人同时过桥,所需要的时间就是走得比较慢的那个人单独行动时所需的时间。问题是,你如何设计一个方案,让用的时间最少。首先让1、2分钟的一起过,...
最短作业优先算法SJF,求平均等待时间
#include #include using namespace std; //最短作业优先算法SJF,求平均等待时间。 float waitingTimeSJF(int *requestTimes, int *durations, int n) { // WRITE YOUR CODE HERE int cpu_time=0; float wait_time=0
最短寻道时间优先算法(SSTF)&&扫描算法(SCAN)
最短寻道时间优先算法(SSTF) SSTF问题描述:SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。 1、算法思想:优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。 2、优点:改善了磁盘平均服务时间。 3、缺点:...
最优乘车问题/dijsktra最短路径算法
H城是一个旅游胜地,每年都有成千上万的人前来观光.为方便游客,巴士公司在各个旅游景点及宾馆、饭店等地都设置了巴士站,并开通了一些单向巴士线路。每条单向巴士线路从某个巴士站出发,依次途径若干个巴士站,最终到达终点巴士站。 阿昌最近到H城旅游,住在CUP饭店。他很想去S公园游玩。听人说,从CUP饭店到S公园可能有也可能没有直通巴士。如果没有,就要换乘不同线路的单向巴士,还有可能无法乘巴士到达。现在用...
趣味算法-城市之间最短总距离
城市之间最短总距离:图为联通图。 (1) 图中所有顶点集合为V, 最小生成树顶点集合为U初始时V包含所有顶点,U为空。 (2) 从V中选取一个顶点V0,将其加入U。 (3) 从V0的邻接顶点中选取边权值最小的Vn,得到最小生成树的一条边,将Vn加入集合U。 (4) 再从V-U中再选取一个与V0, Vn邻接的顶点,找出权值最小的边。 (5) 重复上述步骤。 #incl
数据结构 第15讲 一场说走就走的旅行——最短路径
一场说走就走的旅行——最短路径 本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825 有一天,孩子回来对我说:“妈妈,听说马尔代夫很不错,放假了我想去玩。”马尔代夫?我也想去!没有人不向往一场说走就走的旅行!“其实我想去的地方很多,呼伦贝尔大草原、玉龙雪山、布达拉宫、艾菲尔铁塔……”小孩子还说着他感兴趣的地方。于是
java实现——最短寻道时间优先(SSTF)和扫描(SCAN)算法
模拟实现磁盘调度算法:最短寻道时间优先(SSTF)和扫描(SCAN)算法。实验步骤:理解各调度算法的工作原理对给出的任意的磁盘请求序列、计算平均寻道长度;要求可定制磁盘请求序列长度、磁头起始位置、磁头移动方向。测试:假设磁盘访问序列:98,183,37,122,14,124,65,67;读写头起始位置:53,方向:磁道增加的方向。输入此类数据后,程序按照选定的算法,自动给出访问序列,并且算出经过的...
动态规划求解最短行驶路线问题[Floyd算法]
使用Qt做的演示程序~ 时间是大二下学期的算法分析实践环节。采用Floyd方法求解最短行驶路线问题。
最短时间过桥
本文用代码实现最短时间过桥,并且打印如下两个例子的最小过桥时间: [b] 例子一:[/b]四人夜间过桥,他们只有一个手电筒一次只能两个人过桥,过桥时必须有手电筒,四人过桥时间为1分2分6分10分 [b]例子二:[/b]小明过桥要一秒,小明的弟弟要三秒,小明的爸爸要六秒,小明的妈妈要八秒,小明的爷爷要十二秒。每次此桥最多可过两人,而过桥的速度,依过桥最慢者而定,可是灯在点燃后, 三十秒就会...
极客时间——数据结构与算法(44) 最短路径:地图软件是如何计算出最优出行路径的?
基础篇的时候,我们学习了图的两种搜索算法,深度优先搜索和广度优先搜索。这两种算法主要是针对无权图的搜索算法。针对有权图,也就是图中的每条边都有一个权重,我们该如何计算两点之间的最短路径(经过的边的权重和最小)呢?今天,我就从地图软件的路线规划问题讲起,带你看看常用的最短路径算法(Shortest Path Algorithm)。 像 Google 地图、百度地图、高德地图这样的地图软件,我想你应...
Dijkstra算法解决最短路径问题
本文给出了用Dijkstra算法来解决最短路径问题的程序。 输入如下所示:1 —————–测试用例个数 10 —————–本测试用例的点数 1 2 4 ——————第一个点和第二个点之间的距离是4. 1 3 8 2 3 3 2 4 4 2 5 6 3 4 2 3 5 2 4 5 4 4 6 9 5 6 4 代码如下:#include <stdio.h>#define MA
最短工期 数据结构实现
最短工期(20 分)一个项目由若干个任务组成,任务之间有先后依赖顺序。项目经理需要设置一系列里程碑,在每个里程碑节点处检查任务的完成情况,并启动后续的任务。现给定一个项目中各个任务之间的关系,请你计算出这个项目的最早完工时间。输入格式:首先第一行给出两个正整数:项目里程碑的数量 N(≤100)和任务总数 M。这里的里程碑从 0 到 N−1 编号。随后 M 行,每行给出一项任务的描述,格式为“任务起...
过桥时间最短的算法实现(TopCoder)
问题描述:一群人晚上过桥,每次只能过2个人,并且需要一盏灯。 每个人过桥时间不同。计算最短时间给出是过桥时间如{1,2,5,10},计算出最小时间17首先 1,2 过去 时间 2              1       回来   时间 1        5,10 过去 时间 10       2        回来   时间 2   1,2   过去    时间  2
队列应用银行排队问题模拟改进算法:计算客户的平均停留时间和等待时间以及每个客户的时间信息(VC6.0)
VC6.0!由于生成随机数的需要,程序执行需要3分钟左右的时间。 该算法就相当于是现在银行实行的叫号制度。每个窗口只有一个客户正在办理手续,其它客户都在等待区等待且根据到达事件进行排序,当某个窗口的客户办完业务时,将等待区的最先到达的客户安排到刚空闲下来的窗口去办理业务。这样显然提高了时间利用效率,且先到达的客户办理业务的时间不会晚于后到达的客户。
最短作业优先算法(不完善)
最短作业优先(SJF)是一种调试任务请求的调试策略。每个任务请求都含有请求时间(即向系统提交请求的时间)和持续时间(即完成任务所需时间)属性。当前任务完成后,SJF策略选择最短持续时间的任务执行;如果多个任务具有相同持续时间,那么选择请求时间最早的任务。任务的等待时间为实际开始的时间和请求时间的差值。给定任务的请求时间和持续时间列表,设计一个程序,使用短作业优先算法求所有任务的平均等待时间。
[2017/05/18]操作系统调度算法--最短剩余时间优先算法的模拟实现
看了看上次更博还是3月份。。可怕可怕。果然是因为最近沉迷于读书无法自拔啊qwq(明明是因为懒吧啊喂!)今天看到一道OS题, 题目是这样的: 设有四个进程,它们的到达时刻和处理时间如下所示: 进程 到达时刻 处理时间 P1 , 0 , 8 P2 , 3 , 6
最短寻道时间优先算法(SSTF)
#include #include int cmp(const void* a, const void* b){ return *(int *)a - *(int *)b; } int find(int* g, int len, int n){ int i = 0; for(; i = n) break; return i; } //dn:disk number; cp:curr
最短编辑距离算法(字符串比较)
一、编辑距离 1、从字符串a变为字符串b所需要的元操作有3种: 增加一个字符删除一个字符变化一个字符 2、编辑距离:从字符串a变为b所需要的最少操作步骤。 二、最短编辑距离(动态规划) 首先定义一个函数——step(i, j),它表示第一个字符串的长度为i的子串到第二个字符串的长度为j的子串的编辑距离。 显然可以有如下动态规划公式: if i == 0 且 j =
算法设计课程设计--任务时间表问题
一个单位时间任务是恰好需要一个单位时间完成的任务。给定一个单位时间任务的有限集S.关于S的一个时间表用于描述S中单位时间任务的执行次序。
AOE网关键路径的算法,最最最最直接的算法,一学就会
先了解一下AOE网和关键路径: 如果在有向图中用顶点表示事件,用弧表示活动,用弧上的权表示活动持续时间,称该带权有向图(即有向网)为边表示活动的网(activity on edge network),简称AOE网。 在AOE网中,只有一个顶点代表的事件发生后,从该顶点出发的各个弧所代表的活动才能开始,只有以弧头关联一个顶点的各个弧所代表的活动都已结束,该顶点所代表的事件才能发生。 一项工程可
n个顾客等待时间最短(贪心算法)
设有n个顾客同时等待一个服务。顾客i需要的服务时间为ti(1&amp;lt;=i&amp;lt;=n)。共有s处可以提供此服务。应如何安排n个顾客的服务才能使平均等待时间达到最短?平均的带时间时n个顾客等待服务时间的总和除以n。 方法:先按从大到小排序,然后再挨个排队。 package 实验四; import java.util.Arrays; public class 等待时间最短 { public s...
迪杰斯特拉(dijkstra)算法计算两个地铁站最短距离
前言 由于项目需要计算两个地铁站之前最短距离及其线路流程。 引发使用迪杰斯特拉算法计算带权值两点之前最短距离。 网上资料多用的是C++写的算法,在这里用的是Java。实现的方法可以有很多,重要的是把原理理解后用清晰的代码实现。 这里参考了网上的资料:https://blog.csdn.net/wangchsh2008/article/details/46288967,发现类的职责不十分明确并且逻辑...
021 模拟退火算法学习(一)-----求解最短连通路径
1.模拟退火算法概述 模拟退火是一种通用概率算法,用来在固定时间内寻求在一个大的搜寻空间内找到的最优解。模拟退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所发明。而V. Černý在1985年也独立发明此算法。 模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留
操作系统-磁盘调度算法:先来先服务,最短寻道时间优先,scan算法
1.先来先服务 public class FCFS { /** * 磁盘调度:先来先服务 */ private static int startPosition = 100 ;//磁头开始位置 private static int totalMoving = 0; private static List visitList = new ArrayList();//访问磁道列表
磁盘调度算法;先来先服务调度算法、最短寻道时间优先调度算法、扫描调度算
一、  实验目的和要求1.  了解磁盘调度技术的特点2.  掌握磁盘调度算法,如先来先服务(firstcome first served,FCFS)调度算法、最短寻道时间优先(shortest seek timefirst,SSTF)调度算法、扫描(SCAN)调度算法、循环扫描(C-SCAN)调度算法。二、    实验内容设计模拟实现FCFS、SSTF、SCAN和C-SCAN调度算法的C语言程序。...
磁盘调度算法 电梯调度算法 最短寻道时间调度算法
自己写的磁盘调度算法,通俗易懂,其中有先来先服务调度算法,最短寻道时间调度算法、电梯调度算法
POJ 1700 过河坐船最短时间问题
这道题如果理解了就不难了,可分为一步步两个永远最快的a[0],a[1]载现存的两个最慢的过河的问题,一种是最快a[0]载现存最慢过去,0再回来,再载次慢,0再回来,时间为2*a[0]+a[p-2]+a[p-1],或者01过去,0回来,34过去(不可能0再载3或者4过去,那就浪费了第一次0载1过去的意义,等于在第一种方案基础上把34载过去又把2载过去),2回来,时间为a[0]+2*a[1]+a[p-
dijkstra最短路径及其输出(数学建模)
高中同学让我求8个菜市场和35个销售点(他们之间还会有15个路口)之间35*8=280个组合分别的最短路径及其输出。 最短路水题,嘿嘿。能用自己学到的知识帮助别人解决问题真是极好的享受。 具体注释可以见代码,写的蛮清楚的。 #include #include #include #include #include using namespace std; #define INF 0x3f3f
GIS中最短路径分析——Dijkstra算法
算法思想
单元最短路径问题---Dijkstra算法
最短路径—Dijkstra算法和Floyd算法(理解):https://blog.csdn.net/m0_37345402/article/details/76695930 理解最短路径——迪杰斯特拉(dijkstra)算法:https://www.cnblogs.com/iambupu/p/5713952.html 最短路径问题---Dijkstra算法详解:https://blog.csd...
文章热词 机器学习教程 Objective-C培训 交互设计视频教程 颜色模型 设计制作学习
相关热词 mysql关联查询两次本表 native底部 react extjs glyph 图标 人工智能培训谢谢 java培训最短几个月