Description
There is a funny car racing in a city with n
junctions and m directed roads.
The funny part is: each road is open and closed periodically. Each road is associate with two integers (a,b), that means the road will be open for a seconds, then closed for b seconds, then open for a seconds… All these start from the beginning of the race. You must enter a road when it’s open, and leave it before it’s closed again.
Your goal is to drive from junction s and arrive at junction t as early as possible. Note that you can wait at a junction even if all its adjacent roads are closed.
Input
There will be at most 30 test cases. The first line of each case contains four integers n,m,s,t
(1≤n≤300, 1≤m≤50,000, 1≤s,t≤n). Each of the next m lines contains five integers u,v,a,b,t (1≤u,v≤n, 1≤a,b,t≤105), that means there is a road starting from junction u ending with junction v. It’s open for a seconds, then closed for b seconds (and so on). The time needed to pass this road, by your car, is t. No road connects the same junction, but a pair of junctions could be connected by more than one road.
Output
For each test case, print the shortest time, in seconds. If it’s not possible to arrive at t from s (maybe your car is too slow!), print -1.
Samples
Input Copy
3 2 1 3 1 2 5 6 3 2 3 7 7 6 3 2 1 3 1 2 5 6 3 2 3 9 5 6
Output
Case 1: 20 Case 2: 9
题意：
n个路口，m条街道，每条街道都是有向的
并且这m条街道open a秒 close b秒（循环往复），自己的车通过这条道路需要t秒
可以从路口等待某一条道路open，必须在道路close 之前通过，且必须在另一条道路open的时候进入
问能否从s点到达t点，如果不能，输出-1,如果能输出最短的时间
细节的地方加在了代码里，在建图的过程中，如果说a > t，那么说这条路无论如何是走不过去的，所以干脆直接不建边
priority_queue<int, vector<int>, greater<int>> xiaogen; priority_queue<int, vector<int>, less<int>> dagen; const ll inf = 9223372036854775807; const ll INF = 0x3f3f3f3f; const int maxn = 3e5 + 7; const int mod = 1000000007; #define PI (double)acos(-1.0) #define debug(x) cout << #x << " -> " << x << endl #define IOS \ ios::sync_with_stdio(false); \ cin.tie(NULL); \ cout.tie(NULL); #define lowbit(x) (x & (-x)) #define Clear(x, val) memset(x, val, sizeof x) typedef pair<int, int> PII; int cnt, head[maxn], n, m, s, t; int dis[maxn], vis[maxn]; struct node { int u, v, a, b, t; int nex; } e[maxn]; void add(int u, int v, int a, int b, int t) { e[cnt].u = u, e[cnt].v = v; e[cnt].a = a, e[cnt].b = b, e[cnt].t = t; e[cnt].nex = head[u]; head[u] = cnt++; } void dij() { priority_queue<PII> que; Clear(dis, 0x3f3f3f3f); Clear(vis, false); dis[s] = 0; que.push({0, s}); vis[s] = true; while (que.size()) { PII tp = que.top(); que.pop(); int u = tp.second; vis[u] = false; /// not in the queue for (int i = head[u]; ~i; i = e[i].nex) { int v = e[i].v; /** t1代表到达该点时，道路已经开放多长时间，如果已经开放的时间 + 通过需要的时间 <= 该周期总共开放的时间 说明是可以通过的 否则就需要等待该门重新开放，总共时间 = 等待时间 + 通过时间 在该周期需要等待的时间 = a + b - t1 通过需要的时间即为t 所以总时间为 a + b - t1 + t **/ int t1 = dis[u] % (e[i].a + e[i].b), t2; if (t1 + e[i].t <= e[i].a) t2 = e[i].t; else t2 = e[i].a + e[i].b + e[i].t - t1; if (dis[v] > dis[u] + t2) { dis[v] = dis[u] + t2; if (!vis[v]) que.push({dis[v], v}); } } } } int main() { int _ = 0; while (cin >> n >> m >> s >> t) { Clear(head, -1); cnt = 0; for (int i = 1; i <= m; i++) { int u = read, v = read, a = read, b = read, t = read; if (a < t) continue; add(u, v, a, b, t); } dij(); printf("Case %d: %d\n", ++_, dis[t] == 0x3f3f3f3f ? -1 : dis[t]); } return 0; } /** **/
