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= ;

const LL inf=(LL) ;

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++N,inf) ;

    priority_queue<Node>que ;

    que.push(Node(S,)) ;

    dist[S]= ;

    while(!que.empty()){

        Node now = que.top()  ;

        que.pop() ;

        if(now.u==T){

            return ;

        }

        int u = now.u ;

        for(int i= ; 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= ;

   int u ,v ,open_t ,close_t ,t;

   while(scanf("%d%d%d%d",&N,&M,&S,&T)!=EOF){

        for(int i=;i<=N;i++)

            vec[i].clear()  ;

        for(int i=;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  ;

}

秒客网

The Ninth Hunan Collegiate Programming Contest (2013) Problem F