POJ 2627 Gopher and Hawks：最短路判斷老鼠能否到達

代碼實現 (C++，SPFA/BFS)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Pt { ll x, y; };
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll v, m;
    while (cin >> v >> m) {
        ll maxd = v * m * 60 * 1000; // 放大 1000 後的最大距離
        vector pts;
        double x, y;
        while (cin >> x >> y) {
            pts.push_back({llround(x * 1000), llround(y * 1000)});
        }
        int n = pts.size();
        vector> adj(n);
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                ll dx = pts[i].x - pts[j].x;
                ll dy = pts[i].y - pts[j].y;
                if (dx*dx + dy*dy <= maxd*maxd) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }
        // BFS 求最短路（無權圖）
        vector dist(n, -1);
        queue q;
        dist[0] = 0; q.push(0);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
        if (dist[1] == -1) cout << "No.\n";
        else cout << "Yes, visiting " << dist[1] - 1 << " other holes.\n";
    }
    return 0;
}

複雜度

• 建圖：O(n²)，n ≤ 1000（隱含），約 5e5 邊，可接受。
• BFS：O(n + m)。
• 空間：O(n²) 邊表。

關鍵點

• 浮點坐標 → 整數放大，避免精度誤差導致邊漏判/誤判。
• 無權圖最短路用 BFS 即可，SPFA 過度。
• 輸入以 EOF 結束，每測試用例先讀 v,m，再讀坐標直到文件末尾或下一用例（題目格式需注意，實際 POJ 2627 每用例坐標行數不固定，通常先給 n？原題輸入格式：v m 然後多行坐標直到 EOF 或空行。代碼中用 `while(cin>>x>>y)` 讀完所有坐標）。

這題是「幾何距離建圖 + BFS 最短路」的典型應用，整數放大技巧解決浮點精度問題，代碼清晰實用。