題意#
在 Syrjälä 的網路上有 \(n\) 台電腦以及 \(m\) 條連線。Uolevi 的電腦編號是 1，而 Maija 的電腦編號是 \(n\)。
請判斷 Uolevi 能不能透過這些網路連線傳送訊息給 Maija。如果可以的話，請印出這條路線「最少會經過多少台電腦」，並輸出這條路線的實際經過循序（也就是沿途經過的電腦編號）；如果根本無法連通，就輸出 IMPOSSIBLE。
思路#
這是一道非常經典的「無權重圖最短路徑」問題。\n\n當我們在圖上尋找兩點之間需要最少邊數（或是經過最少節點數）的路線時，廣度優先搜尋（BFS）絕對是我們的不二選擇。因為 BFS 是以同心圓的方式依序向外擴展，第一時間碰觸到終點的路線，保證就是最短的那一條。
與一般的 BFS 稍微不同的是，這題不僅要求長度，還要求還原完整的經過路徑。為此，我們可以準備一個 path 陣列。當我們從節點 A 走到並發現了還沒造訪過的節點 B 時，就在 path[B] 記錄下 A（意思是「B 是從 A 走過來的」）。
當 BFS 找到終點 \(n\) 後（或是整個搜尋結束），我們只要檢查 path[n] 是否有值。如果有，代表我們可以一路從 1 走到 \(n\)；我們就可以從 \(n\) 開始，根據 path 陣列反著追溯回 1，把經過的電腦編號蒐集起來。反轉這個序列後，就是我們要輸出的正確答案了。
程式碼#
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define INF LONG_LONG_MAX/1000
#define WA() cin.tie(0)->sync_with_stdio(0)
#define all(x) (x).begin(), (x).end()
#define int long long
#define PII pair<int, int>
int n, m;
signed main() { WA();
cin >> n >> m;
vector<vector<int>> v(n+1); // 使用鄰接串列儲存圖
vector<int> vis(n+1); // 記錄該台電腦是否已被探索過
// 建立雙向網路連線
while (m--) {
int a, b; cin >> a >> b;
v[a].pb(b);
v[b].pb(a);
}
vector<int> path(n+1); // 用來追蹤路徑：path[u] 代表走到 u 的前一台電腦
queue<int> q;
// 從 Uolevi 的電腦（節點 1）開始 BFS
q.push(1);
while (q.size()) {
int now = q.front(); q.pop();
// 如果已經摸到 Maija 的電腦了，可以提早收工
if (now == n) break;
// 擴展所有相鄰的網路節點
for (auto u : v[now]) if (!vis[u]) {
vis[u] = 1;
path[u] = now; // 記錄 u 是從 now 來的
q.push(u);
}
}
// 檢查是否有辦法抵達終點 n
if (path[n]) {
vector<int> ans;
// 從終點 n 沿著 path 追溯回起點 1
while (n != 1) {
ans.pb(n);
n = path[n];
}
ans.pb(1); // 記得補上起點
// 因為是從終點追溯回來的，經過的電腦數量就是陣列大小
cout << ans.size() << '\n';
// 將路徑反著印出來（從起點前往終點）
for (int i = ans.size()-1; i >= 0; i--) cout << ans[i] << ' ';
cout << '\n';
}
else cout << "IMPOSSIBLE\n";
}
