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秒,现在给你起点、终点、开放的时间、关闭的时间、以及通过关卡所需时间,让你求到达终点所需的最短时间。
分析:用迪杰斯特拉算法的优化队列解决此问题
AC代码:
#include
#include
#include
#include
#include
using namespace std;
#define maxn 300
#define maxm 50000
struct node
{
int x,y,l,r,s;
}edge[2*maxm+5];
int sum[maxn+5];
int vis[maxn+5];
int dis[maxn+5];
int n,m,be,end;
int cmp(node x,node y)
{
return x.x.x;
}
void dijkstra()
{
for(int c=1;c<=n;c++)
{
int min=INT_MAX;