HDU 2923 Einbahnstrasse：Floyd-Warshall 解單向街拖車最短路

HDU 2923 是一道經典的「多源多汇最短路 + 現實建模」題目。城市有 N 個地點（含車庫），C 輛拋錨車輛，R 條單向/雙向道路。拖車必須從車庫出發，依次將每輛車拖回車庫，每次只能拖一輛。求總行駛距離最小值。

一、問題建模關鍵點

1. 圖模型：N ≤ 100 個節點，邊有向且帶長度，可能有重邊（取最小）。
2. 任務序列：車庫 → 車1位置 → 車庫 → 車2位置 → 車庫 …
3. 核心洞察：每次「車庫 ↔ 車位」的往返獨立，總距離 = Σ (最短路車庫→車位 + 最短路車位→車庫)。
4. 同一地點多輛車：輸入列表可能重複，每輛車獨立計算往返。

二、算法選擇：Floyd-Warshall

• N ≤ 100，O(N³) = 10⁶ 極快，完美適配。
• 一次性求出任意兩點最短路，後續查詢 O(1)。
• 處理有向圖、重邊、自環天然無壓力。

三、輸入解析技巧

道路格式三種：

• A -v-> B ：A → B，長度 v
• A <-v- B ：B → A，長度 v
• A <-v-> B ：A ↔ B 雙向，長度 v

掃描時用 scanf("%s %c-%d-%c %s", s1, &c1, &d, &c2, s2)，根據 c1、c2 是 '-' 還是 '<'/'>' 判斷方向。

四、完整 AC 代碼（C++11）

#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 105;

int dist[MAXN][MAXN];
char loc_name[MAXN][110];  // 地點名稱，最長 10 字符 + \0

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, C, R, tc = 0;
    while (cin >> N >> C >> R) {
        if (N == 0 && C == 0 && R == 0) break;
        
        // 初始化距離矩陣
        for (int i = 1; i <= N; ++i)
            for (int j = 1; j <= N; ++j)
                dist[i][j] = (i == j ? 0 : INF);
        
        // 讀取 C+1 個地點：第 0 個是車庫，1~C 是車輛位置
        for (int i = 0; i <= C; ++i) cin >> loc_name[i];
        
        // 映射：地點名稱 → 編號 1..N
        unordered_map<string, int> id;
        int cnt = 0;
        auto get_id = [&](const string& s) {
            if (!id.count(s)) id[s] = ++cnt;
            return id[s];
        };
        
        // 讀取 R 條道路
        for (int i = 0; i < R; ++i) {
            string s1, s2;
            char c1, c2;
            int d;
            cin >> s1 >> c1 >> d >> c2 >> s2;
            int u = get_id(s1), v = get_id(s2);
            if (c1 == '<' && c2 == '>') {      // <-d-> 雙向
                dist[u][v] = min(dist[u][v], d);
                dist[v][u] = min(dist[v][u], d);
            } else if (c1 == '-' && c2 == '>') { // -d-> u→v
                dist[u][v] = min(dist[u][v], d);
            } else if (c1 == '<' && c2 == '-') { // <-d- v→u
                dist[v][u] = min(dist[v][u], d);
            }
        }
        
        // Floyd-Warshall
        for (int k = 1; k <= N; ++k)
            for (int i = 1; i <= N; ++i)
                if (dist[i][k] != INF)
                    for (int j = 1; j <= N; ++j)
                        if (dist[k][j] != INF)
                            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        
        // 計算總距離
        long long total = 0;
        int garage = get_id(loc_name[0]);
        for (int i = 1; i <= C; ++i) {
            int car = get_id(loc_name[i]);
            total += dist[garage][car] + dist[car][garage];
        }
        
        cout << ++tc << ". " << total << '\n';
    }
    return 0;
}

五、關鍵細節總結

1. 地點名稱映射：用 unordered_map<string, int> 動態分配編號，輸入保證出現的地點數 = N。
2. 重邊處理：讀入時取 min，Floyd 會自動傳播最優值。
3. 不可達情況：題目隱含保證所有車位可達車庫，否則 INF 會導致總和溢出，實際可加斷言或判斷。
4. 輸出格式：k. V，k 從 1 開始，點後有空格。

六、複雜度分析

• 時間：O(N³ + R + C)，主導項 N³ = 10⁶，極快。
• 空間：O(N²) 距離矩陣 + O(N) 映射表。

七、舉一反三

• 若 N 較大（如 10⁴），需改用 C 次 Dijkstra（單源最短路）或雙向 Dijkstra。
• 若道路長度會動態更新，需動態最短路算法（如 LCA + 線段樹、或重新跑 Floyd）。
• 本題本質是「多個獨立往返任務的最短路和」，只要任務間無耦合，任意兩點最短路預計算即為最優策略。