CSU 1659 Graph Center：SPFA 多源最短路求圖中心點

問題定義

圖的**中心** = 離心率最小的頂點集合。離心率 ecc(v) = max_u dist(v,u)。圖半徑 r = min_v ecc(v)。中心點即 ecc(v) = r 的點。
給定無向無權圖 N≤100，求所有中心點。

算法選擇：N 次 SPFA / BFS

無權圖最短路用 BFS 即可（O(N+M)），但 SPFA 通用於有權圖。
對每個頂點 s 跑一次 SPFA，得到 dist[s][*]，計算 ecc(s)，最後取最小離心率對應的點。

SPFA 實現要點

int spfa(int s, int n) {
    vector d(n+1, INF);
    queue q; q.push(s); d[s]=0;
    vector inq(n+1); inq[s]=true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u]=false;
        for (int v : G[u]) {
            if (d[v] > d[u] + 1) {
                d[v] = d[u] + 1;
                if (!inq[v]) { q.push(v); inq[v]=true; }
            }
        }
    }
    return *max_element(d.begin()+1, d.begin()+n+1);
}

完整流程

int main() {
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> n >> m;
        G.assign(n+1, {});
        for (int i=0;i>u>>v; G[u].push_back(v); G[v].push_back(u); }
        vector ecc(n+1);
        for (int i=1;i<=n;++i) ecc[i] = spfa(i, n);
        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);
        cout << center.size() << "\n";
        for (int i=0;i