CSU 1659 Graph Center 另解：Floyd-Warshall 全對最短路求圖中心

Floyd-Warshall 適用性

N ≤ 100，O(N³) = 1e6 操作，極適合 Floyd 算法。代碼比 SPFA 更短，無需佇列，常數小。

核心代碼

const int INF = 0x3f3f3f3f;
int dist[105][105];

int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        for (int i=1;i<=n;++i)
            for (int j=1;j<=n;++j)
                dist[i][j] = (i==j) ? 0 : INF;
        for (int i=0;i>u>>v;
            dist[u][v] = dist[v][u] = 1;
        }
        // Floyd
        for (int k=1;k<=n;++k)
            for (int i=1;i<=n;++i)
                for (int j=1;j<=n;++j)
                    if (dist[i][k] + dist[k][j] < dist[i][j])
                        dist[i][j] = dist[i][k] + dist[k][j];
        // 計算離心率
        vector ecc(n+1);
        for (int i=1;i<=n;++i) {
            int mx = 0;
            for (int j=1;j<=n;++j) mx = max(mx, dist[i][j]);
            ecc[i] = mx;
        }
        int radius = *min_element(ecc.begin()+1, ecc.end());
        vector center;
        for (int i=1;i<=n;++i) if (ecc[i]==radius) center.push_back(i);
        // 輸出
    }
}

與 SPFA 對比

本題 N=100 時 Floyd 更快且代碼最簡潔，推薦使用。

注意事項

• 初始化 dist[i][i]=0，其他 INF。
• 無向圖雙向賦值 1。
• 圖保證連通（M ≥ N-1），無需處理不可達情況。