这道题主要比较权值的时候要改变一下，其他地方基本一样。

比较权值的时候要考虑边的时间与a， b

可以设相对于当前边的时间now， 则now = d[u] % （a+b）， 也就是当前这个边进行到整个a和b的循环

的哪个地方了。然后我们分类讨论。

（1）当t >a的时候， 这种边在输入的时候就可以去掉了， 因为不管什么情况都走不了。打开的时间不足以

通过

（2）可以直接过的时候。这个时候now + t <= a， 也就是说当前的时刻加上过的时间仍然在打开的时间。

那么总时间就是d[u]+t， 就直接松弛就ok了。

（3）需要“等待”的时候。如果不符合（2）那个不等式， 那么就是需要等待。我们需要求出等待的时间。

等待的时间就是下一次开启的时间到目前时间的时间差， 也就是a+b-now。那么总时间就是d[u]+t + wait

然后松弛就ok了。

ps：（1）标号按照题目的来， 从一开始还是从0开始要注意。

         （2）开始在纠结当前时间加上过边的时间不一定就是最优的时间，   因为过边的时间与哪一个点有关。

后来想通了， 还是自己不是很理解dijsktra， 谁说一定要当前的路径加上边的路径最优？当前的这条路径就是

最短路， 然后一个点一个点去拓展， 最后一定都是最短路。

#include
    
     #include
     
      #include
      
       #define REP(i, a, b) for(int i = (a); i < (b); i++)using namespace std;const int MAXN = 312;struct Edge{	int v, w, a, b;	Edge(int v, int a, int b, int w) : v(v), a(a), b(b), w(w) {};};struct node{	int u, d;	node(int u = 0, int d = 0) : u(u), d(d) {};	bool operator < (const node& rhs) const	{		return d > rhs.d;	}};vector
       
         g[MAXN];int d[MAXN], n, m, s, t;int solve(){	REP(i, 1, n + 1) d[i] = (i == s ? 0 : 1e9);	priority_queue
        
          q;	q.push(node(s, 0));		while(!q.empty())	{		node x = q.top(); q.pop();		int u = x.u;		if(d[u] != x.d) continue;				REP(i, 0, g[u].size())		{			Edge& e = g[u][i];			int v = e.v, w = e.w, a = e.a, b = e.b;			int now = d[u] % (a + b);						if(now + w <= a)			{				if(d[v] > d[u] + w)				{					d[v] = d[u] + w;					q.push(node(v, d[v]));				}			}						else			{				int wait = a + b - now; 				if(d[v] > d[u] + w + wait)				{					d[v] = d[u] + w + wait;					q.push(node(v, d[v]));				}			}		}	}		return d[t];}int main(){	int kase = 0;	while(~scanf("%d%d%d%d", &n, &m, &s, &t))	{		REP(i, 0, n) g[i].clear();		REP(i, 0, m)		{			int u, v, w, a, b;			scanf("%d%d%d%d%d", &u, &v, &a, &b, &w);			if(w <= a) g[u].push_back(Edge(v, a, b, w));		}		printf("Case %d: %d\n", ++kase, solve());	}	return 0;}