Problem: https://vjudge.net/problem/UVA-10986
題目摘要：
有 n 台SMTP伺服器透過 m 條網絡線連接，每條網絡線連接兩台伺服器，透過每條網絡線發送電子郵件有一定的延遲時間（以毫秒為單位）。 假設伺服器本身不會造成延遲，請問沿著網絡線從伺服器 S 向伺服器 T 發送電子郵件所需的最短時間是多少？
Solution: Calculate the shortest path using Dijkstra algorithm
解題想法：Dijkstra algorithm 計算最短路徑
實作：priority_queue (多數情況快一些) 或 set
| Implementation | Time on Virtual Judge |
| priority_queue | 100% (180 ms) |
| set | 111% (200 ms) |
| set (with st.erase() ) | 111% (200 ms) |
目錄
【做法1】priority_queue
- vector G[maxn]: 存圖 (adjacency list)
- dist[maxn]: 紀錄起點到每一點的最短距離，初始設為INF，起點設成 0。
- priority_queue<P, vector<P>, greater<P> > pq: 記錄尚未拓展的頂點，指定greater<P>來依照first由小到大排序。first 是最短距離，second是頂點編號。
- Line-38：dist[p.S] < p.F 表示頂點 v 已經被拓展過了。
#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
#define pii pair<int, int>
#define P pair<long long, int>
#define F first
#define S second
#define INF 0x3F3F3F3F3F3F3F3F
const int maxn = 20000;
vector<pii> G[maxn];
long long dist[maxn];
int main() {
int N, n, m, S, T;
int u, v, w;
cin >> N;
for (int Case=1; Case<=N; Case++){
for (int i=0; i<maxn; i++) G[i].clear();
cin >> n >> m >> S >> T;
for (int i=0; i<m; i++){
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
// Dijkstra - priority_queue
memset(dist, 0x3F, sizeof(dist));
priority_queue<P, vector<P>, greater<P> > pq;
dist[S] = 0;
pq.push({0, S});
while (!pq.empty()){
P p = pq.top();
pq.pop();
if (dist[p.S] < p.F) continue;
for (auto nxt: G[p.S]){
if (dist[nxt.F] > dist[p.S] + nxt.S){
dist[nxt.F] = dist[p.S] + nxt.S;
pq.push({dist[nxt.F], nxt.F});
}
}
}
cout << "Case #" << Case << ": ";
if (dist[T] == INF) cout << "unreachable\n";
else cout << dist[T] << '\n';
}
return 0;
}
【做法2】set
- vector G[maxn]: 存圖 (adjacency list)
- dist[maxn]: 紀錄起點到每一點的最短距離，初始設為INF，起點設成 0。
- set<P> st: 記錄尚未拓展的頂點，依照first由小到大排序。first 是最短距離，second是頂點編號。
- Line-41：N不是很大時，可略。
#include <iostream>
#include <cstring>
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define pii pair<int, int>
#define P pair<long long, int>
#define F first
#define S second
#define INF 0x3F3F3F3F3F3F3F3F
const int maxn = 20000;
vector<pii> G[maxn];
long long dist[maxn];
int main() {
int N, n, m, S, T;
int u, v, w;
cin >> N;
for (int Case=1; Case<=N; Case++){
for (int i=0; i<maxn; i++) G[i].clear();
cin >> n >> m >> S >> T;
for (int i=0; i<m; i++){
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
// Dijkstra - set
memset(dist, 0x3F, sizeof(dist));
set<P> st;
dist[S] = 0;
st.insert({0, S});
while (!st.empty()){
P p = *st.begin();
st.erase(p);
if (dist[p.S] < p.F) continue;
for (auto nxt : G[p.S]){
long long new_dist = p.F + nxt.S;
if (new_dist < dist[nxt.F]){
//st.erase({dist[nxt.F], nxt.F});
dist[nxt.F] = new_dist;
st.insert({dist[nxt.F], nxt.F});
}
}
}
cout << "Case #" << Case << ": ";
if (dist[T] == INF) cout << "unreachable\n";
else cout << dist[T] << '\n';
}
return 0;
}