UVA 11374 Airport Express：Dijkstra + 枚舉商業線優化最短路

問題描述

機場快線分經濟線和商業線，擁有一張商業線車票（最多乘坐一段商業線）。給定圖中兩類邊，求從起點 S 到終點 T 的最短時間，並輸出路徑及是否使用商業票。

核心洞察

若使用商業線邊 (u, v)，則路徑必為：
S --(經濟線)--> u --(商業線)--> v --(經濟線)--> T
即：起點到 u、v 到終點均只能走經濟線。

算法流程

1. 構建僅含經濟線邊的圖。
2. 從 S 跑 Dijkstra 得 distS[]、preS[]（最短路樹）。
3. 從 T 跑 Dijkstra 得 distT[]、preT[]（反向最短路樹）。
4. 初始答案 ans = distS[T]（全程經濟線）。
5. 枚舉每條商業線邊 (u, v, w)（雙向考慮 u→v 和 v→u）：
   • 候選距離 cand = distS[u] + w + distT[v]
   • 若 cand < ans，更新 ans 並記錄最佳商業邊 (best_u, best_v)。
6. 輸出路徑：
   • 未用商業票：輸出 preS 回溯路徑，打印 "Ticket Not Used"
   • 用了商業票：輸出 S→best_u (按 preS 逆序)、best_v→T (按 preT 正序)、商業邊端點、總耗時

關鍵優化

• 優先隊列優化 Dijkstra：O((V+E) log V)，避免 O(V²) TLE。
• 邊數組足夠大：題目說邊 ≤ 1000，但雙向+商業線枚舉需開 ≥ 10000 否則 RE。
• 路徑重建：利用前驅數組 preS/preT 正確拼接輸出格式。

程式碼框架（關鍵部分）

// 圖結構
struct Edge { int u, v, w, next; } edges[MAXM];
int head[MAXN], ecnt;
void addEdge(int u, int v, int w) { ... }

// Dijkstra with priority_queue
void dijkstra(int src, int dist[], int pre[]) {
    priority_queue, vector>, greater>> pq;
    fill(dist, dist+n+1, INF);
    dist[src] = 0; pq.emplace(0, src);
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) continue;
        for (int e = head[u]; ~e; e = edges[e].next) {
            int v = edges[e].v, w = edges[e].w;
            if (dist[v] > d + w) {
                dist[v] = d + w;
                pre[v] = u;
                pq.emplace(dist[v], v);
            }
        }
    }
}

// 主邏輯
dijkstra(S, distS, preS);
dijkstra(T, distT, preT);
ans = distS[T];
for (each business edge (u,v,w)) {
    if (distS[u] + w + distT[v] < ans) { ... }
    if (distS[v] + w + distT[u] < ans) { ... }
}
// 輸出路徑邏輯...

複雜度

• 兩次 Dijkstra：O((N+M) log N)
• 枚舉商業線：O(K) (K ≤ 1000)
• 總體極快。

總結

UVA 11374 展示了「預處理 + 枚舉關鍵決策」的經典模式：將「最多用一次特殊資源」轉化為枚舉該資源使用位置，兩側用預處理最短路瞬時評估。此技巧廣泛適用於「最多 K 次特殊操作」、「必經某類邊」等變體最短路問題。