HDU 1385 Minimum Transport Cost：Floyd-Warshall 路徑重建與字典序

題目大意

給定 N ≤ 100 個城市的運費矩陣（-1 表示不通）與各城市稅費，多次查詢從 s 到 t 的最小總費用（含中轉城市稅費），並輸出字典序最小的路徑。

Floyd-Warshall 核心遞推

dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j] + tax[k])

其中 tax[k] 為中轉城市 k 的稅費（起點、終點不收稅）。

路徑重建與字典序策略

• 維護 path[i][j] 為從 i 到 j 的字典序最小路徑（vector<int>）。
• 初始化：path[i][j] = {i, j}（若直連）。
• 鬆弛時：

if (dist[i][k] + dist[k][j] + tax[k] < dist[i][j]) {
    dist[i][j] = dist[i][k] + dist[k][j] + tax[k];
    path[i][j] = path[i][k];
    path[i][j].pop_back(); // 移除重複的 k
    path[i][j].insert(end, path[k][j].begin(), path[k][j].end());
}
else if (dist[i][k] + dist[k][j] + tax[k] == dist[i][j]) {
    vector<int> cand = path[i][k];
    cand.pop_back();
    cand.insert(cand.end(), path[k][j].begin(), path[k][j].end());
    if (cand < path[i][j]) path[i][j] = move(cand); // vector 內建字典序比較
}

完整 C++ 實作

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int N;
    while (cin >> N && N) {
        vector<vector<int>> dist(N, vector<int>(N));
        for (int i=0;i> dist[i][j];
                if (dist[i][j] == -1) dist[i][j] = INF;
            }
        vector<int> tax(N);
        for (int& x : tax) cin >> x;
        vector<vector<vector<int>>> path(N, vector<vector<int>>(N));
        for (int i=0;i> s >> t && s != -1 && t != -1) {
            --s; --t;
            cout << "From " << s+1 << " to " << t+1 << " :\nPath: ";
            for (size_t i=0;i";
                cout << path[s][t][i]+1;
            }
            cout << "\nTotal cost : " << dist[s][t] << "\n\n";
        }
    }
    return 0;
}

關鍵細節

1. 稅費 tax[k] 僅在 k 作為中轉點時加入，起點、終點不收稅（Floyd 自然滿足）。
2. 字典序比較直接用 `vector` 的 `operator<`。
3. 路徑合併時注意去重中間節點 k。
4. 輸出格式嚴格遵循樣例（空行、箭頭、大小寫）。

複雜度

• 時間：O(N³)，N≤100 完全足夠。
• 空間：O(N³) 存儲所有路徑（100³ ≈ 1e6 整數，約 4MB）。