Cave Raider
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
*
Source
题目类型：最短路
算法分析：和一般的最短路问题不同，这里的每条边都能够进行多次的松弛，相当于每条边有多个边权，具体来说就是只有在开门区间内移动才能松弛一条边，且边权需要按照当前的情况进行计算
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
/************************************************* Author :supermaker Created Time :2016/3/23 22:29:05 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 666; int n, m, s, t; struct Node { int v, w, nxt; vector <int> val; }; vector <Node> edge[maxn]; int dis[maxn]; bool inq[maxn]; void spfa () { for (int i = 0; i < maxn; i++) dis[i] = INF; dis[s] = 0; memset (inq, false, sizeof (inq)); queue <int> qu; qu.push (s); inq[s] = true; while (!qu.empty ()) { int tt = qu.front (); qu.pop (); inq[tt] = false; for (int i = 0; i < edge[tt].size (); i++) { if (dis[tt] < INF) { Node te = edge[tt][i]; int len = te.val.size (); bool is_odd; for (int j = 1; j < len; j++) { if (j & 1) is_odd = true; else is_odd = false; if (is_odd && dis[tt] + te.w <= te.val[j] && te.val[j-1] + te.w <= te.val[j]) { int res = max (dis[tt], te.val[j-1]); if (dis[te.v] > res + te.w) { dis[te.v] = res + te.w; if (!inq[te.v]) { inq[te.v] = true; qu.push (te.v); } } } } } } } } int main() { //CFF; //CPPFF; while (cin >> n) { if (n == 0) break; cin >> m >> s >> t; string s; getline (cin, s); for (int i = 0; i < maxn; i++) edge[i].clear (); for (int i = 1; i <= m; i++) { getline (cin, s); stringstream ss (s); int u, v, w; ss >> u >> v >> w; Node tt; tt.v = v, tt.w = w; tt.val.push_back (0); int vval; while (ss >> vval) tt.val.push_back (vval); tt.val.push_back (INF); edge[u].push_back (tt); tt.v = u; edge[v].push_back (tt); } spfa (); if (dis[t] == INF) cout << "*" << endl; else cout << dis[t] << endl; } return 0; } |