# 題目: UVa 11792 - Krochanska is Here
# 題目說明
給 m 條路線，其中有重複的車站稱為 重點車站 ，求哪一個 重點車站 到其他所有 重點車站 的距離最短
(題目中文翻譯可參考: 天然呆 翻譯 UVa 11792 Krochanska is Here!)
INPUT:
第一行輸入一個整數 t ，代表測資數
每筆測資先輸入兩個整數 n 、 m ， n 為車站數、 m 為路線數
接下來有 m 行，每行輸入數個整數，代表此路線的車站，以 0 當作結尾
OUTPUT:
輸出哪一個 重點車站 到其他所有 重點車站 的距離最短
# 解題方法
此題為 dijkstra 演算法的應用
先建表，由於車站到車站是雙向的，屬於無向圖，所以需要建雙邊
使用 cross 紀錄車站是否為 重點車站
對每個 重點車站 跑 dijkstra 演算法，找尋此 重點車站 到其他每個 重點車站 的距離
因為所有車站到車站的距離都視為相同，所以不需要紀錄 weight ， dijkstra 使用普通的 queue 即可，不需要使用 priority queue
最後再比對哪個 重點車站 到其他所有 重點車站 的距離最短
# 參考程式碼
#include <iostream> | |
#include <vector> | |
#include <climits> | |
#include <queue> | |
using namespace std; | |
static auto fast_io = [] | |
{ | |
ios::sync_with_stdio(false); | |
cout.tie(nullptr); | |
cin.tie(nullptr); | |
return 0; | |
}(); | |
vector< vector<int> > G; | |
vector<int> cross; | |
int dijkstra(int root, int n) | |
{ | |
vector<int> dist(n + 1, INT_MAX); | |
vector<bool> vis(n + 1, false); | |
queue<int> Q; | |
int cnt = 0; | |
dist[root] = 0; | |
Q.push(root); | |
while (!Q.empty()) | |
{ | |
int u = Q.front(); Q.pop(); | |
for (auto& i : G[u]) | |
{ | |
if (dist[i] > dist[u] + 1) | |
{ | |
dist[i] = dist[u] + 1; | |
if (!vis[i]) vis[i] = true, Q.push(i); | |
} | |
} | |
} | |
for (int i = 1; i <= n; ++i) | |
{ | |
if (cross[i] <= 1) continue; | |
cnt += dist[i]; | |
} | |
return cnt; | |
} | |
int main() | |
{ | |
int t, n, m; | |
cin >> t; | |
while (t--) | |
{ | |
cin >> n >> m; | |
int v, u; | |
int Min = INT_MAX, ret = 0; | |
G.assign(n + 1, vector<int>()); | |
cross.assign(n + 1, 0); | |
while (m--) | |
{ | |
cin >> v; | |
++cross[v]; | |
while (cin >> u, u) | |
{ | |
G[v].push_back(u); | |
G[u].push_back(v); | |
++cross[u]; | |
v = u; | |
} | |
} | |
for (int i = 1; i <= n; ++i) | |
{ | |
if (cross[i] <= 1) continue; | |
int cnt = dijkstra(i, n); | |
if (cnt < Min) ret = i, Min = cnt; | |
} | |
cout << "Krochanska is in: " << ret << "\n"; | |
} | |
} |
# 參考資料
https://m80126colin.github.io/blog/articles/%E7%BF%BB%E8%AD%AF/uva/uva11792/
https://theriseofdavid.github.io/2021/09/14/UVa/UVa11792/
