UVA 12661 Funny Car Racing （Dijkstra最短路）

題意：

在一個賽車比賽中，有n 個交叉點和m 個單向道路，每條道路周期性的開啟a秒，關閉b秒，通過時間是t秒， 求從S到T 的最短時間？

思路：

和正常的迪傑斯特拉一樣，存的是時間，優先時間小的先彈出。

隻不過在壓入隊列中 分情況讨論：

1.如果現在的時間能進入這條道路，并且能在道路關閉之前出來，就進入隊列。

2.否則就等這條道路在開啟時 在進入隊列。

吐槽：

會有重邊的存在，寫成vector 存邊就過去了= =

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#define Siz(x) (int)x.size()
using namespace std;
int n,m ,s,t,ks;
const int oo = 5e7+10;
struct Node{
    int c,d;
    bool operator < (const Node& rhs) const {
        return d > rhs.d;
    }
    Node(int c=0,int d=0):c(c),d(d){}
};
struct Edge{
    int u,v,a,b,t;
    void read(){
        scanf("%d %d %d %d %d",&u, &v, &a, &b, &t);
    }
}p;
priority_queue<Node>q;
vector <Edge>edges;
int dp[307];
vector<int>g[307];
bool vis[307];
void dij(){
    for (int i = 0; i <= n; ++i){
        vis[i] = 0;
        dp[i] = oo;
    }
    dp[s] = 0;
    while(!q.empty()) q.pop();
    q.push(Node(s,0));
    while(!q.empty()){
        Node u = q.top(); q.pop();
        int c = u.c;
        if (vis[c])continue;
        vis[c] = 1;
        for (int i = 0; i < Siz(g[c]); ++i){
            int v = g[c][i];
            Edge& e = edges[v];
            v = e.v;
            int a = e.a,b = e.b, t = e.t;
            int dd = dp[c] % (a+b);
            if (t > a) continue;
            if (dd + t > a){
                if (dp[v] > dp[c] + a+b-dd+t){
                    dp[v] = dp[c]+a+b+t-dd;
                    q.push(Node(v,dp[v]));
                }
            }
            else {
                if (dp[v] > dp[c] + t){
                    dp[v] = dp[c] + t;
                    q.push(Node(v,dp[v]));
                }
            }
        }
    }
}
int main(){
    while(~scanf("%d %d %d %d",&n ,&m, &s, &t)){
        for (int i = 0; i <= n; ++i)g[i].clear();
        edges.clear();
        for (int i = 0; i < m; ++i){
            p.read();
            int u = p.u, v = p.v;
            edges.push_back(p);
            g[u].push_back(i);
        }
        dij();
        printf("Case %d: %d\n",++ks,dp[t]);
    }
    return 0;
}
/**
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

Case 1: 20
Case 2: 9
**/