2 shunfurh shunfurh 于 2017.09.04 19:10 提问

Trip the Lights Fantastic

Problem Description
Bob Roberts (father of Little Bobby of problem D) works at the Traffic Commission for a medium size town. Bob is in charge of monitoring the traffic lights in the city and dispatching repair crews when necessary. Needless to say, Bob has a lot of free time, so to while away the hours he tries to figure out the quickest way to take short trips between various points in the city. Bob has at his disposal a lot of information: the layout of streets in the city and the location and cycle times for all of the traffic lights. To simplify the solution process, he makes the following assumptions:

  1. All cars travel at the same top speed, and, if sitting at a red light, take 5 seconds to react and get up to speed. (That is, Bob assumes the car is essentially standing still for 5 seconds, then proceeds at top speed. Bob also assumes the light will not have turned back to red in the 5 seconds it takes to get going.)

  2. Each car approaches a light at full speed and either passes through the light if it is green or yellow, or comes to an immediate stop if it is red. Cars are allowed to pass through a light if they hit it just as it is turning to green. Cars must stop if they reach the light just as it is turning to red.

  3. The time to make turns through a light is ignored. It is possible to travel between any two lights, although perhaps not directly.

Furthermore, no u-turns are allowed nor will routes revisit an intersection. Even given these assumptions, Bob has difficulty coming up with minimum time paths. Let’s see if you can help him.

Input
The first line of each test case will contain four positive integers n, m, s, and e, where n (2 ≤ n ≤ 100) is the number of traffic lights (numbered 0 through n - 1), m is the number of roads between the traffic lights, and s and e (s ≠ e) are the starting and ending lights for the desired trip. There will then follow n lines of the form g y r indicating the number of seconds that each light is green, then yellow, then red. (1 ≤ g, y, r ≤ 100.) The first of these lines refers to light 0, the second to light 1, and so on. Following these n lines will be m lines, each describing one road. These lines will have the form l1 l2 t, where l1 and l2 are the two lights being connected by the road and t is the time (in seconds, t ≤ 500) to travel the length of the road at full speed — you should add 5 to this value to obtain the travel time when driving the road beginning at a standstill. All roads are two way. At time 0, all lights are just starting their green period and your car is considered to be at a standstill at traffic light s. Since it takes 5 seconds to get going, you may assume that g + y is never less than or equal to 5. The last test case is followed by a line containing 0 0 0 0 indicating end-of-input.

Output
For each test case, output a single line containing the minimum time to travel from the start light to the end light. Output your results in the form mm:ss indicating the number of minutes and seconds the trip takes. If the number of seconds is less than 10 then preface it with a 0 (i.e., output 4:05, not 4:5). Likewise, if the number of minutes is less than 10, print just one digit (as in 4:05).

Sample Input
3 3 0 2
3 4 5
3 3 3
2 4 4
0 1 1
1 2 2
0 2 12
3 3 0 2
3 4 5
3 4 3
2 4 4
0 1 1
1 2 2
0 2 12
0 0 0 0

Sample Output
0:16
0:08

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.19 05:27
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Gym 101194F Mr. Panda and Fantastic Beasts
Gym 101194F Mr. Panda and Fantastic Beasts2016acm-icpc 中国赛区总决赛 F题 后缀自动机题意给n个字符串,找第一个字符串的一个最短子串,使得它不是2到n任何一个字符串的子串。输出字典序最小的。思路SAM。算半个裸题? %%%把2到n用特殊字符连接起来(‘z’+1),拼成一个字符,构建sam。然后用第一个字符串跟他匹配,每次失配时更新答案。sa
Gym101194F-Mr. Panda and Fantastic Beasts
题意:给你n个字符串,找出一个最短的字符串,使得这个字符串只是第一个字符串的子串 解题思路:后缀数组+二分 #include #include #include #include #include #include #include #include #include #include #include #include #include using nam
错误输入(Trip_Zone)子模块的工作特性
错误输入信号                              ~ ,在低电平时,表示输入了一个错误信号,错误事件发生。每个EPWM模块可以被独立地配置为使能或者禁止这个错误输入信号 。如果要在特定的EPWM模块中使能,可通过EPWM模块的TZSEL寄存器来设置。        输入可以同步系统时钟(SYSCLKOUT)输入,也可以作为异步信号输入,同时,作为复用的IO, 信号
Gym - 101194F Mr. Panda and Fantastic Beasts [2016-2017 ACM-ICPC CHINA-Final] [后缀数组]
点击打开题目 题意: 求第一个字符串在其他字符串中未出现过的最短, 且字典序最小的子串. 分析: 先将所有子串用特殊字符串连接起来, 用后缀数组算出子串的sa数组和lcp高度数组, 然后从后往前遍历, 遇到长度更小的更新答案即可.  #include #include #include #include #include #include #include typedef l
Gym - 101194F Mr. Panda and Fantastic Beasts (后缀数组)
题意:给出n个字符串,找到最短的字符串,要求仅为第一个字符串的子串。 思路:把n个字符串用不出现的字符连接起来。其实就是枚举第一个字符串的每一个子串是否是其他字符串的后缀的前缀即可。 #include #include #include #include #include using namespace std; const int MAXN=400000+10; const i
雅思听力听写练习之 C7T2-2--Boat Trip
这次听写感觉大部分的词还是能听明白的,但是,需要断句,长句子听完,记不出清楚,短句子能写下来。大约听了半个小时,这一篇才算完成。      下面是听写的记录:
he is finding this trip very exciting
<br />Why ing?<br /> <br />be finding 可理解成“发现”<br /> <br />http://zhidao.baidu.com/question/88761913.htmlfind+宾语+形容词做宾补<br /> find trip exciting;find the room clean<br /> 注意,在本句中用的是find的进行时态。<br /><br /> 在收听外台的广播中经常能听到find不用一般式,而用进行式。<br /> eg:We're fi
2DDL Pro 2D Dynamic Lights and Shadows
2DDL系统 是一个Unity软件包,它具有2D环境的Light系统。 2DDL的工作原理类似于一个真正的Light,但在二维中,射线从中心源投射,并与称为对撞机的障碍发生冲突。 这个障碍建立最后的光,并显示阴影效果。 2DDL是完全动态的,这意味着如果你改变或移动光源或障碍物,最终结果会受到实时影响。
POJ-1222 EXTENDED LIGHTS OUT(高斯消元)
题意: 给你一个5*6的矩阵,每个点上都有一个灯,按下f[i][j]的按钮,f[i][j]位置的灯的状态会改变,它上下左右的灯的状态也会改变(开变关,关变开)。 现在给出这个矩阵的初始状态,输出按下哪些按钮,使所有的灯都关闭。 做法: 利用高斯消元解异或方程组。 用x[i][j]表示第i行第j列的灯是否被按下 x[i][j] ^  x[i+1][j] ^  x[i-1][j]
UVA 1560 - Extended Lights Out(高斯消元)
UVA 1560 - Extended Lights Out 题目链接 题意:给定一个矩阵,1代表开着灯,0代表关灯,没按一个开关,周围4个位置都会变化,问一个按的方法使得所有灯都变暗 思路:两种做法: 1、枚举递推 这个比较简单,就枚举第一行,然后递推过去,每次如果上一行是亮灯,则下一行开关必须按下去 2、高斯消元, 这个做法比较屌一些,每个位置对应上下左右中5个位