HLJOJ 1015 變形多源最短路徑：Floyd + 排序優化選址

問題重述

N 個村莊，K 條有向路，每村有電話亭。需選一村作為中心電話亭，所有快遞員往返中心報到。另有 M 部電話，裝電話的村莊無需往返。求快遞員總路程最小值。

解題策略

1. Floyd-Warshall 計算任意兩村間最短路 (N≤200，O(N^3) 可行)
2. 對每村 i 計算 sum[i] = Σ (dis[i][j] + dis[j][i])，即所有村往返 i 的總距離
3. 選 sum 最小的村作為中心
4. 將所有村往返中心的距離存入數組，降序排序
5. 減去最大的 M 個值（裝電話的村節省的往返距離）

核心代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 200, INF = 1e7;
int dis[MAXN][MAXN], n, m, k;

void Floyd() {
    for (int k=0; k INF) printf("No solution\n");
        else printf("%d\n", minSum);
    }
    return 0;
}

關鍵細節

• 有向圖：dis[i][j] 不一定等於 dis[j][i]
• Floyd 初始化：對角線 0，其餘 INF
• 中心選擇後，節省距離為 dis[center][i] + dis[i][center]
• 若結果仍大於 INF，說明存在不可達村莊，輸出 "No solution"

複雜度

• Floyd: O(N^3) = 8×10^6 操作，極快
• 排序: O(N log N)
• 總體輕鬆通過