Browse Problem: https://vjudge.net/problem/UVA-12661
摘錄翻譯：
在一個有n個交叉路口和m條道路的城市中，有一個趣味賽車活動。
有趣的是：每條道路會定期開放和封閉。 每條道路都有兩個整數參數（a，b），表示這條道路將開放a秒鐘，然後封閉b秒，然後開放a秒鐘… 時間從比賽開始時計算。 您必須在道路開放時進入道路，並且在道路關閉前離開它。目標是從路口s出發，並儘早抵達路口t。
注意：道路是單向的。
注意：即使所有相鄰道路都封閉時，也可以在路口等候。
注意：沒有道路的兩端是同一個路口，但兩個路口可能有多種連結方式。
解題想法：使用Dijkstra計算最短路徑。
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define maxn 305
struct node{
int v;
long long a, b, t;
node(int _v, long long _a, long long _b, long long _t): v(_v), a(_a), b(_b), t(_t) {}
};
// 存圖
vector<node> g[maxn];
// 紀錄該點是否已找到最短距離且向外拓展過
int exp[maxn];
// 紀錄起點到此點的最短距離,初始設為INF,起點設成0
long long dist[maxn];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, src, dst;
int u, v;
long long a, b, t;
int Case = 1;
while (cin >> n >> m >> src >> dst) {
memset(exp, 0, sizeof(exp));
memset(dist, 0x3F, sizeof(dist));
for (int i=0; i<maxn; i++){
g[i].clear();
}
dist[src] = 0;
for (int i=0; i<m; i++) {
cin >> u >> v >> a >> b >> t;
if (a >= t) g[u].push_back(node(v, a, b, t));
}
// Dijkstra
set<pair<long long,int> > st; // 記錄尚未拓展的節點的最新狀態
st.insert({0, src});
long long Time=0, new_Time=0;
int cur = -1;
while (!st.empty()){
auto now = *st.begin();
st.erase(now);
if (exp[now.second]) continue;
Time = now.first;
cur = now.second;
for (auto nxt : g[cur]){
if (Time % (nxt.a + nxt.b) <= (nxt.a - nxt.t)){
new_Time = Time + nxt.t;
}else{
new_Time = Time + nxt.a + nxt.b - (Time % (nxt.a + nxt.b)) + nxt.t;
}
if (new_Time < dist[nxt.v]){
st.erase({dist[nxt.v], nxt.v});
dist[nxt.v] = new_Time;
st.insert({dist[nxt.v], nxt.v});
}
}
exp[cur] = 1;
}
cout << "Case " << Case++ << ": ";
cout << dist[dst] << '\n';
}
return 0;
}