【题意】
在一个赛车比赛中，赛道有(n(n<=300))个交叉点和(m(m<=50000))条单向道路。有趣的是，每条道路都是周期性关闭的。每条道路用5个整数(u,v,a,b,t)组成。((1<=u,v<=n,1<=a,b,t<=10^5))，表示起点是(u)，终点是(v)，通过的时间为(t)秒。另外，这条路会打开(a)秒，然后关闭(b)秒，然后再打开(a)秒...依次类推。当比赛开始时，每条道路刚刚打开。你的赛车必须在道路打开时进入该道路，并且在它关闭前离开（进出道路不耗费时间，也就是说你可以在打开的瞬间进入，在关闭的瞬间离开）。
你的任务是从(s)出发，尽早到达目的地(t(1<=s,t<=n))。道路的起点和终点不会相同，但是有可能两条道路的起点和终点分别相同 （也就是说可能有重边，但不会有自环）
【算法】
( ext{最短路})
【分析】
本题是一道最短路问题，但是与别的问题不同的是：花费的总时间并不是经过每条边的通过时间之和，还要加上在每个点的等待总时间。我们仍然调用标准的最短路算法（这里用(Dijkstra)），计算边权要分情况讨论。
分情况讨论边权
-
该道路处于关闭状态：边权=通过时间+（关闭时间-已关闭时间）
-
该道路处于开启状态
-
剩下的开启时间足够通过：边权=通过时间
-
剩下的开启时间不够通过：边权=通过时间+关闭时间+（开启时间-已开启时间）
-
那我们要怎么判断一条道路是否开启或关闭呢？
答案是 (res= ext{时间})%(( ext{开启时间}+ ext{关闭时间}))。如果(res> ext{开启时间})，说明此道路关闭，反之此道路开启（自己想一想，应该能相通的）
【代码】
细节上面已经说的很清楚了 （也方便进行复制），就不加注释了
#include<bits/stdc++.h>
using namespace std;
const int MAXN=350;
int n,m,s,t;
vector<int>ver[MAXN];
vector<int>edge[MAXN];
vector<int>a[MAXN],b[MAXN];
bool vis[MAXN];
int d[MAXN];
int T;
struct Node
{
int pos,dis;
bool operator < (const Node &x) const
{
return x.dis<dis;
}
};
inline int read()
{
int tot=0;
char c=getchar();
while(c<'0'||c>'9')
c=getchar();
while(c>='0'&&c<='9')
{
tot=tot*10+c-'0';
c=getchar();
}
return tot;
}
inline void dijkstra()
{
priority_queue<Node>q;
while(q.size())q.pop();
q.push((Node){s,0});
d[s]=0;
while(q.size())
{
Node now=q.top();
q.pop();
int x=now.pos,y=now.dis;
if(vis[x])continue;
vis[x]=1;
for(int i=0;i<ver[x].size();i++)
{
int tt=ver[x][i];
int res=y%(a[x][i]+b[x][i]);
if(res>=a[x][i])
{
if(res-a[x][i]==0&&b[x][i]+edge[x][i]+y<d[tt])
{
d[tt]=b[x][i]+edge[x][i]+y;
if(!vis[tt])q.push((Node){tt,d[tt]});
}
else if(res-a[x][i]>0&&b[x][i]-(res-a[x][i])+edge[x][i]+y<d[tt])
{
d[tt]=b[x][i]-(res-a[x][i])+edge[x][i]+y;
if(!vis[tt])q.push((Node){tt,d[tt]});
}
}
else
{
if(a[x][i]-res>=edge[x][i]&&edge[x][i]+y<d[tt])
{
d[tt]=edge[x][i]+y;
if(!vis[tt])q.push((Node){tt,d[tt]});
}
else if(a[x][i]-res<edge[x][i]&&edge[x][i]+y+b[x][i]+a[x][i]-res<d[tt])
{
d[tt]=edge[x][i]+y+b[x][i]+a[x][i]-res;
if(!vis[tt])q.push((Node){tt,d[tt]});
}
}
}
}
}
int main()
{
while(scanf("%d%d%d%d",&n,&m,&s,&t)!=EOF)
{
memset(vis,0,sizeof(vis));
memset(d,0x3f,sizeof(d));
for(int i=1;i<=n;i++)
{
ver[i].clear();edge[i].clear();
a[i].clear();b[i].clear();
}
for(int i=1;i<=m;i++)
{
int x1=read(),x2=read(),x4=read(),x5=read(),x3=read();
if(x3>x4)continue;
ver[x1].push_back(x2);
edge[x1].push_back(x3);
a[x1].push_back(x4);
b[x1].push_back(x5);
}
//cout<<d[t]<<endl;
dijkstra();
printf("Case %d: %d
",++T,d[t]);
}
return 0;
}