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. It’s always possible to arrive at t from s.
Sample Input
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
Sample Output
Case 1: 20 Case 2: 9
Source 湖南省第九届大学生计算机程序设计竞赛
思路：基本上是很裸的spfa，在松弛条件处改一下就好了。
有一个坑点就是，那条路的t有可能大于a。（具体详见代码）
代码：
#include<stdio.h> #include<queue> #include<string.h> #include<algorithm> using namespace std; #define mem(a,b) memset(a,b,sizeof(a)) #define maxn 100000+10 #define maxv 1000+10 const int inf=0x3f3f3f3f; typedef long long LL; LL n,m,len; struct node { LL v,a,b,t,next; }G[maxn]; LL d[maxv],first[maxv],inq[maxv]; void spfa(LL st,LL ed) { for(LL i=1;i<=n;i++) { d[i]=100000000000000; inq[i]=0; } d[st]=0,inq[st]=1; queue<LL>q; q.push(st); while(!q.empty()) { st=q.front(); q.pop(); inq[st]=0; for(LL i=first[st];i!=-1;i=G[i].next) { LL v=G[i].v,a=G[i].a,b=G[i].b,t=G[i].t; LL cnt=(d[st]%(a+b)),tot; if(t>a) continue; if(cnt<=a) { if((cnt+t)<=a) tot=d[st]+t; else tot=a-cnt+b+t+d[st]; } else tot=d[st]+a+b-cnt+t; if(d[v]>tot) { d[v]=tot; if(!inq[v]) { inq[v]=1; q.push(v); } } } } printf("%lld\n",d[ed]); } void add_egde(LL u,LL v,LL a,LL b,LL t) { G[len].v=v,G[len].a=a,G[len].b=b,G[len].t=t; G[len].next=first[u]; first[u]=len++; } int main() { LL T=1,st,ed; while(~scanf("%lld%lld%lld%lld",&n,&m,&st,&ed)) { len=0; mem(first,-1); LL u,v,a,b,t; for(LL i=0;i<m;i++) { scanf("%lld%lld%lld%lld%lld",&u,&v,&a,&b,&t); add_egde(u,v,a,b,t); } printf("Case %lld: ",T++); spfa(st,ed); } return 0; }