传送门：点击打开链接
题意：给你有向图，每条边呈周期性开放，即开放a时间，再关闭b时间，再开放a时间以此类推
如果时间不足以穿过这条路则不能走，你可以在节点等待时间，问从s走到t所需要的最小时间
仔细想一想这题，对于某条边，越早走到u点一定是最优的，大不了我就等时间嘛
所以，这只是一个普通的dijistra然后稍微在每一条边的距离上做了点手脚而已
在节点等待时间，我们可以认为是某一条路的长度增加了，所以只要在读取边长度的时候，稍微处理一下等待时间，就可以了
需要注意的地方：
1.如果开放时间小于边的长度，这条边是无论怎样都不能通过的，所以一开始就不能把这条边添加进去
2.如果到达某一点时，这条边是开放的，但是剩下的开放时间已经不足以通过这条边，那么要等到关闭后，重新开放时，才能通过
#include<map>
#include<set>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
#define FIN freopen("input.txt","r",stdin)
#define FOUT freopen("output.txt","w+",stdout)using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<LL, int> PLI;const int MX = 1e5 + 5;
const int INF = 0x3f3f3f3f;int Head[MX], Next[MX], rear;struct Edge {int u, v, cost, a, b;
} E[MX];void edge_init() {rear = 0;memset(Head, -1, sizeof(Head));
}void edge_add(int u, int v, int cost, int a, int b) {E[rear].u = u;E[rear].v = v;E[rear].cost = cost;E[rear].a = a;E[rear].b = b;Next[rear] = Head[u];Head[u] = rear++;
}LL d[MX];
void dijistra(int Begin) {memset(d, INF, sizeof(d));d[Begin] = 0;priority_queue<PLI, vector<PLI>, greater<PLI> >work;work.push(PLI(0, Begin));while(!work.empty()) {PLI f = work.top();work.pop();LL dist = f.first;int u = f.second;for(int id = Head[u]; ~id; id = Next[id]) {int tq = E[id].a + E[id].b, time = dist % tq, add = 0;if(time > E[id].a || time + E[id].cost > E[id].a) add = tq - time;int cost = E[id].cost + add, v = E[id].v;if(dist + cost < d[v]) {d[v] = dist + cost;work.push(PLI(dist + cost, v));}}}
}int main() {int n, m, s, t, ansk = 0; //FIN;while(~scanf("%d%d%d%d", &n, &m, &s, &t)) {edge_init();for(int i = 1; i <= m; i++) {int u, v, a, b, cost;scanf("%d%d%d%d%d", &u, &v, &a, &b, &cost);if(a >= cost) edge_add(u, v, cost, a, b);}dijistra(s);printf("Case %d: %lld\n", ++ansk, d[t]);}return 0;
}