Funny Car Racing

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
一些赛道，打开a分钟，关闭b分钟，如此循环，问车从起点到终点的最少时间。
直接迪杰斯特拉，把赋值操作表达式改成题目中要求的就好了，原理上还是找最小时间，只是表达式不一样而已。
其实就是贪心的bfs。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
struct Node{
    int u, v, a, b, t;
}node[50005];
int dp[305], leap[305];
void check(int num, int time)
{
    int temp;
    temp = time % (node[num].a + node[num].b);
    if (node[num].t <= node[num].a)
    {
        if (temp + node[num].t > node[num].a)
        {
            int temp1;
            temp1 = time - temp + node[num].a + node[num].b + node[num].t;
            dp[node[num].v] = min(dp[node[num].v], temp1);
        }
        else
            dp[node[num].v] = min(dp[node[num].v], time + node[num].t);
    }
}
int main()
{
    int i, j, m, n, ans, t, s, kase = 1;
    while (scanf("%d%d%d%d", &n, &m, &s, &t) != EOF)
    {
        for (i = 1; i <= m; i++)
            scanf("%d%d%d%d%d", &node[i].u, &node[i].v, &node[i].a, &node[i].b, &node[i].t);
        for (i = 1; i <= n; i++)
            dp[i] = inf;
        dp[s] = 0;
        memset(leap, 0, sizeof(leap));
        leap[s] = 1;
        for (i = 1; i <= m; i++)
        {
            if (node[i].u == s)
                check(i, 0);
        }
        for (i = 1; i <= 305; i++)
        {
            int tempx, tempm;
            tempx = tempm = inf;
            for (j = 1; j <= n; j++)
            {
                if (!leap[j] && dp[j] <= tempm)
                {
                    tempm = dp[j];
                    tempx = j;
                }
            }
            if (tempx == inf)break;
            leap[tempx] = 1;
            for (j = 1; j <= m; j++)
            {
                if (node[j].u == tempx)
                    check(j, dp[tempx]);
            }
        }
        cout << "Case " << kase++ << ": ";
        cout << dp[t] << endl;
    }
    return 0;
}