The Ninth Hunan Collegiate Programming Contest (2013) Problem F

Problem F

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<=10⁵), 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

Output for the Sample Input

Case 1: 20
Case 2: 9

The Ninth Hunan Collegiate Programming Contest (2013) Problemsetter: Rujia Liu Special Thanks: Md. Mahbubul Hasan

很明显的快速最短路，满足最优性，用堆优化，扩展边的时候判断2种情况。注意边是有向边。万变不离其宗。

#include <iostream>
#include <stdio.h>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
#include <set>
#include <algorithm>
#include <map>
#include <stack>
#include <math.h>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std ;
typedef long long LL ;
const int Max_N=308 ;
const LL inf=(LL)1000000000000000000 ;
struct Road{
    int V ;
    LL open_time ;
    LL close_time ;
    LL T ;
    Road(){} ;
    Road(int v ,LL o ,LL c ,LL t):V(v),open_time(o),close_time(c),T(t){} ;
};
vector<Road>vec[Max_N] ;
int N ,M ,S ,T ;
struct Node{
    int u ;
    LL Time ;
    Node(){} ;
    Node(int U ,LL t):u(U),Time(t){} ;
    friend bool operator < (const Node A ,const Node B){
         return A.Time>B.Time ;
    }
};
LL dist[Max_N] ;
void spfa(){
    fill(dist,dist+1+N,inf) ;
    priority_queue<Node>que ;
    que.push(Node(S,0)) ;
    dist[S]=0 ;
    while(!que.empty()){
        Node now = que.top()  ;
        que.pop() ;
        if(now.u==T){
            return ;
        }
        int u = now.u ;
        for(int i=0 ; i<vec[u].size() ;i++){
            Road r=vec[u][i] ;
            int v = r.V ;
            LL o_t = r.open_time ;
            LL c_t = r.close_time ;
            LL t = r.T ;
            if(r.T > o_t)
                continue ;
            LL res = ( now.Time%(o_t+c_t)+(o_t+c_t) ) % (o_t+c_t) ;
            if(res+t<=o_t&&now.Time+t<dist[v]){
                dist[v]=now.Time+t ;
                que.push(Node(v,dist[v]));
            }
            else if(now.Time+o_t+c_t-res+t<dist[v]){
                dist[v] = now.Time+o_t+c_t-res+t ;
                que.push(Node(v ,dist[v])) ;
            }
        }
    }
}
int main(){
   int k=1 ;
   int u ,v ,open_t ,close_t ,t;
   while(scanf("%d%d%d%d",&N,&M,&S,&T)!=EOF){
        for(int i=1;i<=N;i++)
            vec[i].clear()  ;
        for(int i=1;i<=M;i++){
            scanf("%d%d%d%d%d",&u,&v,&open_t,&close_t,&t) ;
            vec[u].push_back(Road(v,(LL)open_t,(LL)close_t,(LL)t)) ;
           // vec[v].push_back(Road(u,(LL)open_t,(LL)close_t,(LL)t)) ;
        }
        spfa() ;
        printf("Case %d: ",k++) ;
        cout<<dist[T]<<endl ;
   }
   return 0 ;
}