您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

HDU 1385 Minimum Transport Cost：Floyd 最短路 + 字典序最小路徑

編輯：C++ 入門

HDU 1385 - 城市運輸最小費用：Floyd-Warshall + 路徑字典序

N≤50 城市，邊權 a[i][j]（-1 表示無邊），過路費 b[i]。多組查詢 c→d，求最小總費用（路徑邊權和 + 經過中間城市過路費和），若多解輸出字典序最小路徑。

Floyd 變種：過路費內化

松弛條件：
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j] + cost[k])
其中 cost[k] 為城市 k 的過路費。源點和終點不收費，故 Floyd 過程中 k 作為中介點時加費，完美建模。

字典序最小路徑：記錄後繼而非前驅

path[i][j] = 從 i 到 j 的第一步（後繼）。初始 path[i][j]=j。
鬆弛時：

if (tmp < dis[i][j] || (tmp == dis[i][j] && path[i][j] > path[i][k])) {
    dis[i][j] = tmp;
    path[i][j] = path[i][k]; // 經 k 的第一步 = i→k 的第一步
}

打印路徑：
u = st; while (u != en) { print(u); u = path[u][en]; } print(en);
從前向後打印，天然字典序最小（因優先選擇最小後繼）。

完整代碼結構

void floyd() {
    for (k=1..n) for (i=1..n) for (j=1..n)
        if (dis[i][k]+dis[k][j]+cost[k] < dis[i][j] || 
            (== && path[i][j] > path[i][k])) {
            dis[i][j] = ...; path[i][j] = path[i][k];
        }
}
void solve() {
    while (scanf("%d%d",&st,&en), st!=-1) {
        printf("From %d to %d :\nPath: %d", st,en,st);
        for (int u=st; u!=en; u=path[u][en]) printf("-->%d", u);
        printf("\nTotal cost : %d\n\n", dis[st][en]);
    }
}