2 shunfurh shunfurh 于 2017.09.19 17:25 提问

Cave Raider

Description

Afkiyia is a big mountain. Inside the mountain, there are many caves. These caves are connected by tunnels. Hidden in one of the caves is a terrorist leader. Each tunnel connects two caves. There could be more than one tunnels connect the same two caves.
At the joint of a tunnel and a cave, there is a door. From time to time, the terrorists close a tunnel by shutting the two doors at the two ends, and "clean" the tunnel. It is still a mystery how they clean the tunnel. However, we know that if a person (or any living creature) is trapped in the tunnel when it is being cleaned, then the person (or the living creature) will die. After a cleaning of the tunnel is finished, the door will open, and the tunnel can be used again.
Now the intelligence servicemen have found out which cave the leader is hiding,and moreover, they know the schedule of the cleaning of the tunnels. Jing Raider is going to go into the cave and catch the leader. You need to help him find a route so that he can get to that cave in the shortest time. Be careful not to be trapped in a tunnel when it is being cleaned.
Input

The input consists of a number of test cases. The 1st line of a test case contains four positive integers n,m, s, t, separated by at least one space, where n is the number of caves (numbered 1, 2, ... , n), m is the number of tunnels (numbered 1, 2, ... ,m), s is the cave where Jing is located at time 0, and t is the cave where the terrorist leader is hiding. (1 <= s, t <= n <= 50 and m <= 500).
The next m lines are information of the m tunnels: Each line is a sequence of at most 35 integers separated by at least one space. The first two integers are the caves that are the ends of the corresponding tunnel. The third integer is the time needed to travel from one end of the tunnel to the other. This is followed by an increasing sequence of positive integers (each integer is at most 10000) which are alternately the closing and the opening times of the tunnel. For example, if the line is
10 14 5 6 7 8 9
then it means that the tunnel connects cave 10 and cave 14, it takes 5 units of time to go from one end to the other. The tunnel is closed at time 6, opened at time 7, then closed again at time 8, opened again at time 9. Note that the tunnel is being cleaned from time 6 to time 7, and then cleaned again from time 8 to time 9. After time 9, it remains open forever.
If the line is
10 9 15 8 18 23
then it means that the tunnel connects cave 10 and cave 9, it takes 15 units of time to go from one end to the other. The tunnel is closed at time 8, opened at time 18,then closed again at time 23. After time 23, it remains closed forever.
The next test case starts after the last line of the previous case. A 0 signals the end of the input.
Output

The output contains one line for each test case. Each line contains either an integer, which is the time needed for Jing to get to cave t, or the symbol *, which means that Jing can never get to cave t. Note that the starting time is 0. So if s = t, i.e., Jing is at the same cave as the terrorist leader, then the output is 0.
Sample Input

2 2 1 2
1 2 5 4 10 14 20 24 30
1 2 6 2 10 22 30
6 9 1 6
1 2 6 5 10
1 3 7 8 20 30 40
2 4 8 5 13 21 30
3 5 10 16 25 34 45
2 5 9 22 32 40 50
3 4 15 2 8 24 34
4 6 10 32 45 56 65
5 6 3 2 5 10 15
2 3 5 2 9 19 25
2 2 1 2
1 2 7 6 9 12
1 2 9 8 12 19
0
Sample Output

16
55
*

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.05 00:09
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
POJ 1613 Cave Raider
SPFA过的。 虽然很麻烦,其实就是加上一个限制条件的最短路。 题意是说给你一些点,一些边,起点与终点。 然后这些边通过的时候需要花费时间,但是也有开关限制。 问你到达重点的最短路。(无向图) 比如输入: 1 2 6 2 10 22 30 表示 1 -> 2 需要花费时间为 6。 0~1         ,  1~2          ,  2~3         
poj 1613 Cave Raider
Cave Raider Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 870   Accepted: 268 Description Afkiyia is a big mountain. Inside the mountain, there are many
POJ-1613 Cave Raider
Cave Raider Time Limit: 1000MS   Memory Limit: 10000K Description Afkiyia is a big mountain. Inside the mountain, there are many caves. These caves are connected by tunnels. Hidde
poj 1613 Cave Raider 最短路
很简单的最短路,只是加上了一定的限制条件。         首先读取时做下处理,把开放时间小于通行时间的去掉。         做最短路的时候判断好逻辑关系即可         注意,这题输入有问题,可能行尾有空格之类的 /* author:jxy lang:C/C++ university:China,Xidian University **If you need to repr
poj 1613 Cave Raider (SPFA)
Cave Raider Time Limit: 1000MS   Memory Limit: 10000K Total Submissions: 744   Accepted: 230 Description Afkiyia is a big mountain. Inside the mountain, there are many ca
《the cave》攻略及感悟
《the cave》这款游戏是一个智力解谜游戏,寒假太无聊,又不想刷题,于是把这个游戏给通关了,哈哈。        我玩的是汉化版的,里面的英语基本上不到1/3吧,贴个链接吧:《the cave》《the cave》        游戏开始给你七个有各自技能的人:时空穿越者(穿越栅栏)僧侣(隔空取物) 双生子(召唤出魂保持原有动作) 骑士(无敌)  乡巴佬(在水里游泳)  女
POJ 1613/ZOJ 1791 Cave Raider(bellman-ford)
链接:http://poj.org/problem?id=1613 这题被无向边坑了很久,wa了好多次,最后从有向边改成无向边就过了。 样例解释: 2 2 1 2 1 2 5 4 10 14 20 24 30 1 2 6 2 10 22 30 第一行表示:2个点,2种边,起点,终点 第二行的1 2 5表示从1到2,权值为5(当然,这是无向边,反方向也是),后面的4,10,14
Codeforces Round #461 (Div. 2) C. Cave Painting(数论 思维)
C. Cave Paintingtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputImp is watching a documentary about cave painting.Some numbers, carved in chaotic o...
codeforces 922 C Cave Painting
能同时满足n mod i = i -1 (i = 1, 2, 3, ..., k)的n有多少个呢?
UVA1442 Cave
题解:从左往右扫描,初始时设水位level=s[0],然后依次判断各个位置[i,i+1]处的高度1. 如果p[i] > level,说明水被隔绝了,需要把level提升到pi2. 如果s[i] < level,说明水位太高,碰到天花板,需要把level降低到si3. 位置[i,i+1]处的水位就是扫描到位置i时的level代码#include <cstdio> #include <queue> #i