题目：http://ch.ezoj.tk/contest/CH%20Round%20%2357%20-%20Story%20of%20the%20OI%20Class/导航软件
题解：刚开始看见题目，这不是裸的分层图spfa吗？
于是开始写代码，读边的时候忽然发现居然还有红绿灯，我说不会这么简单的，那这题一定很神。。。
于是滚去做vijos
看了题解一口血喷出来啊。。。
事后想了想，貌似不管红绿灯什么事，走多少是多少？来的早至少不会比来得迟的过得晚。。。
T_T
计算有红绿灯时通过的时间时需要好好yy一下，注释写在代码里
代码：
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<string>
#define inf 1000000000
#define maxn 50005
#define maxm 500+100
#define eps 1e-10
#define ll long long
#define pa pair<int,int>
#define for0(i,n) for(int i=0;i<=(n);i++)
#define for1(i,n) for(int i=1;i<=(n);i++)
#define for2(i,x,y) for(int i=(x);i<=(y);i++)
#define for3(i,x,y) for(int i=(x);i>=(y);i--)
#define mod 1000000007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=*x+ch-'';ch=getchar();}
return x*f;
}
struct edge{int go,next,w,t1,t2;}e[*maxn];
int n,m,k,s,t,tot,d[maxn][],head[maxn];
queue<pa> q;
bool v[maxn][];
inline void insert(int x,int y,int t1,int t2,int z)
{
e[++tot].go=y;e[tot].w=z;e[tot].next=head[x];head[x]=tot;e[tot].t1=t1;e[tot].t2=t2;
e[++tot].go=x;e[tot].w=z;e[tot].next=head[y];head[y]=tot;e[tot].t1=t1;e[tot].t2=t2;
}
int calc(int ti,int t1,int t2,int t)
{
if(!t2)return ti+t;
if(!t1)return inf;
int res=ti;
while(t)
{
int tmp=res%(t1+t2);
if(!tmp)
{
if(t%t1)res+=t/t1*t2+t;//需要走t/t1个时间段，而在此之间等待的时间就为t/t1*t2
else res+=(t/t1-)*t2+t;//少等待一个t2，因为最后一次已经走过这条路
t=;
}
else if(tmp<t1)
{
if(t<=t1-tmp)res+=t,t=;
else res+=t1-tmp,t-=t1-tmp;//暴力模拟只走这一段
}
else res+=t1+t2-tmp;//等待
}
return res;
}
int spfa()
{
memset(d,,sizeof(d));
d[s][]=;q.push(pa(s,));
while(!q.empty())
{
int x=q.front().first,z=q.front().second;q.pop();v[x][z]=;
for(int i=head[x];i;i=e[i].next)
{
int y=e[i].go;
if(z<k&&d[x][z]+e[i].w<d[y][z+])
{
d[y][z+]=d[x][z]+e[i].w;
if(!v[y][z+]){v[y][z+]=;q.push(pa(y,z+));}
}
int tmp=calc(d[x][z],e[i].t1,e[i].t2,e[i].w);
if(tmp<d[y][z])
{
d[y][z]=tmp;
if(!v[y][z]){v[y][z]=;q.push(pa(y,z));}
}
}
}
int ans=inf;
for0(i,k)ans=min(ans,d[t][i]);
return ans;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
n=read();m=read();k=read();
for1(i,m)
{
int x=read(),y=read(),t1=read(),t2=read(),z=read();
insert(x,y,t1,t2,z);
}
s=read();t=read();
printf("%d\n",spfa());
return ;
}