HDU 1869 六度分離：Floyd 判斷圖直徑 ≤ 6

問題描述

給定 n（< 100）個人，m（< 200）對認識關係。判斷任意兩人之間最短路徑長度是否 ≤ 6。多測試案例。

Floyd-Warshall 算法

n ≤ 100，O(n³) = 10⁶ 運算，極快。
初始化 dist[i][j] = (i==j?0:INF)，讀入邊設 1。
三重循環松弛，最後檢查所有 dist[i][j] <= 6。

完整代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f, MAXN = 105;
int dist[MAXN][MAXN];
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    int n, m;
    while (cin >> n >> m) {
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dist[i][j] = (i == j) ? 0 : INF;
        for (int i = 0; i < m; ++i) {
            int a, b; cin >> a >> b;
            dist[a][b] = dist[b][a] = 1;
        }
        for (int k = 0; k < n; ++k)
            for (int i = 0; i < n; ++i)
                for (int j = 0; j < n; ++j)
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        bool ok = true;
        for (int i = 0; i < n && ok; ++i)
            for (int j = 0; j < n; ++j)
                if (dist[i][j] > 6) { ok = false; break; }
        cout << (ok ? "Yes" : "No") << '\n';
    }
    return 0;
}

複雜度

O(n³) 時間，O(n²) 空間，完全滿足限制。