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

// 就....
// 噼里啪啦 噼里啪啦 简简单单最短路
#include <cstring>
#include <cstdio>
#include <iostream>
#include <queue>
#define Maxn 305
using namespace std;
bool vis[Maxn];
int head[Maxn],tot,dis[Maxn];

struct Node {// Dijkstra的状态节点
    int v,dis;
    bool operator < (const Node &that) const {
        return dis > that.dis;
    }
};
struct Edge{
    int v,next,open,close,t;
}e[50005];
inline void Add_Edge(int u,int v,int a,int b,int t) {
    e[++tot].v = v,e[tot].open = a,e[tot].close = b;
    e[tot].t = t; e[tot].next = head[u]; head[u] = tot;
}

int Dijkstra(int S,int T) {
    memset(dis,0x7f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    priority_queue<Node> q;
    dis[S] = 0;
    q.push((Node){S,0});
    while(!q.empty()) {
        Node x = q.top(); q.pop();
        int u = x.v;
        if(u == T) return x.dis;
        vis[u] = true;
        for(int i=head[u]; i; i=e[i].next) {
            int v = e[i].v;
            int progress = dis[u] % (e[i].close + e[i].open);
            if(progress + e[i].t <= e[i].open) {// 可以直接通过
                if(dis[v] > dis[u] + e[i].t) {
                    dis[v] = dis[u] + e[i].t;
                    q.push((Node){v,dis[v]});
                }
            }
            else { // 当前剩余的时间不够通过   需要等待一定时间
                int waiting = e[i].open + e[i].close - progress;
                if(dis[v] > waiting + dis[u] + e[i].t) {
                    dis[v] = waiting + dis[u] + e[i].t;
                    q.push((Node){v,dis[v]});
                }
            }
        }
    }
    return dis[T];
}

int main(int argc,char* argv[]) {
    int n,m,kase = 0,S,T;
    while(scanf("%d %d %d %d",&n,&m,&S,&T) != EOF) {
        tot = 0;
        memset(head,0,sizeof(head));
        for(int u,v,a,b,c,i=1; i<=m; i++) {
            scanf("%d %d %d %d %d",&u,&v,&a,&b,&c);
            if(c <= a) Add_Edge(u,v,a,b,c);
        }
        printf("Case %d: %d\n",++kase,Dijkstra(S,T));
    }
    //system("pause");
    return 0;
}