Funny Car Racing CSU - 1333 （spfa）-白红宇

Funny Car Racing CSU - 1333 （spfa）

阅读量：5106 次

发布时间：2019-06-13

本文共 2733 字，大约阅读时间需要 9 分钟。

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#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             //STL数值算法头文件#include
             
              #include 
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   //模板类头文件using namespace std;typedef long long ll;const int maxn=1100;const int INF=0x3f3f3f3f;struct node{ ll to, next ; ll a, b, c, d ;} E[50010];ll id, head[maxn] ;ll dis[maxn] ;bool vis[maxn];void init(){ id = 0; memset(head, -1, sizeof(head)); for(ll i = 0 ; i < maxn ; i++) dis[i] = INF ;}void addEdg(ll u, ll v, ll a, ll b, ll c){ E[id].to = v ; E[id].a = a ; E[id].b = b ; E[id].c = c ; E[id].d = a + b ; E[id].next = head[u] ; head[u] = id++;}void spfa(ll s, ll t){ memset(vis,0,sizeof(vis)); queue
                   
                    q; dis[s] = 0 ; vis[s]=1; if(s != t ) q.push( s ) ; while(!q.empty()) { ll u = q.front() ; q.pop() ; vis[u] = 0 ; for(ll i = head[u] ; i!=-1; i=E[i].next) { ll v = E[i].to ; ll tt = E[i].a - (dis[u]%E[i].d); if(tt
                    
                      dis[u] + tt +E[i].c) { dis[v] = dis[u] + tt +E[i].c ; if(!vis[v]&&v!=t) { vis[v] = 1; q.push(v); } } } }}int main(){ ll n, m, s, t, u, v, a, b, c ; ll T = 0; while(~scanf("%lld%lld%lld%lld",&n,&m,&s,&t)) { init(); while(m--) { scanf("%lld%lld%lld%lld%lld",&u, &v, &a, &b, &c) ; if(c<=a) addEdg( u, v, a, b, c ); } spfa(s, t ) ; if(dis[t]==INF) dis[t] = -1; printf("Case %lld: %lld\n",++T,dis[t]); }}

转载于:https://www.cnblogs.com/nyist-xsk/p/7264829.html

你可能感兴趣的文章