POJ 2449 Remmarguts' Date 第 K 短路 (A* 算法模板)

問題

有向圖 n≤1000, m≤100000，求從 S 到 T 的第 K 短路長度 (K≤1000)。允許重複經過節點，路徑長度相同但邊序列不同視為不同路徑。不存在輸出 -1。

A* 算法核心

評價函數 `f = g + h`：
- `g`：從起點到當前節點的實際距離。
- `h`：當前節點到終點的最短距離估計 (啟發函數)。
若 `h` 是精確的最短距離 (可行啟發)，則 A* 保證按路徑長度非遞減順序擴展節點，第 K 次彈出終點即為第 K 短路。

實現步驟

1. 反向圖從 T 跑 SPFA/Dijkstra 求所有節點到 T 的最短距離 `h[u]`。
2. 正向圖從 S 用優先隊列 (按 f 排序) 執行 A*。
3. 彈出終點計數 +1，第 K 次輸出 g。
4. 特判：S==T 時 K++ (因空路徑長度 0 被計為第 1 短)。

代碼框架 (C++)

struct State { int u, g, f; bool operator<(State o) const { return f==o.f ? g>o.g : f>o.f; } };
int h[MAXN], dist[MAXN];
vector adj[MAXN], rev[MAXN];

void spfa(int t) { /* 反向圖求 h */ }

int astar(int s, int t, int k) {
    if (s == t) ++k;
    if (h[s] == INF) return -1;
    priority_queue pq;
    pq.push({s, 0, h[s]});
    int cnt = 0;
    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        if (cur.u == t) { if (++cnt == k) return cur.g; }
        for (auto &e : adj[cur.u]) {
            int v = e.to, ng = cur.g + e.w;
            pq.push({v, ng, ng + h[v]});
        }
    }
    return -1;
}

複雜度

SPFA O(m) 平均，A* 最多擴展 K 條路徑相關節點，實際極快。K≤1000 保證效率。