POJ 2449 Remmarguts' Date：K 短路 A* 算法（SPFA 預處理 + 優先隊列搜索）

問題描述

有向圖 n (≤ 1000) 點、m (≤ 100000) 邊。給定起點 s、終點 t、整數 k。求從 s 到 t 的第 k 短路長度（允許重複經過點/邊）。不可達輸出 -1。

A* 算法框架

1. 預處理：反向圖上從 t 跑 SPFA（或 Dijkstra），得到 h[u] = u 到 t 的最短距離。若 h[s] = INF 則無解。
2. A* 搜索：狀態 (u, g, f)，g = 從 s 到 u 的實際路長，f = g + h[u] 為估值函數。優先隊列按 f 再 g 升序。
3. 從 (s, 0, h[s]) 開始，每次取出 f 最小狀態展開。到達 t 計數 cnt++，當 cnt == k 返回 g。
4. 特殊情況：s == t 時，第 1 短路為 0（空路徑），需將 k++。

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 1010;
const int MAXM = 100010;

struct Edge { int to, w, next; } e[MAXM], rev[MAXM];
int head[MAXN], rhead[MAXN], ecnt;
int h[MAXN];
bool inq[MAXN];

void addEdge(int u, int v, int w) {
    e[ecnt] = {v, w, head[u]}; head[u] = ecnt;
    rev[ecnt] = {u, w, rhead[v]}; rhead[v] = ecnt++;
}

void spfa(int t) {
    fill(h, h+MAXN, INF); memset(inq, 0, sizeof(inq));
    queue<int> q; q.push(t); h[t] = 0; inq[t] = true;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = false;
        for (int i = rhead[u]; ~i; i = rev[i].next) {
            int v = rev[i].to, w = rev[i].w;
            if (h[v] > h[u] + w) {
                h[v] = h[u] + w;
                if (!inq[v]) { inq[v] = true; q.push(v); }
            }
        }
    }
}

struct State {
    int u, g, f;
    bool operator<(const State& o) const {
        return f != o.f ? f > o.f : g > o.g; // 小根堆
    }
};

int astar(int s, int t, int k) {
    if (s == t) ++k; // 空路徑為第1短
    if (h[s] == INF) return -1;
    priority_queue<State> 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 (int i = head[cur.u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            pq.push({v, cur.g + w, cur.g + w + h[v]});
        }
    }
    return -1;
}

int main() {
    int n, m;
    while (~scanf("%d%d", &n, &m)) {
        fill(head, head+MAXN, -1);
        fill(rhead, rhead+MAXN, -1);
        ecnt = 0;
        for (int i = 0; i < m; ++i) {
            int u, v, w; scanf("%d%d%d", &u, &v, &w);
            addEdge(u, v, w);
        }
        int s, t, k; scanf("%d%d%d", &s, &t, &k);
        spfa(t);
        printf("%d\n", astar(s, t, k));
    }
    return 0;
}

複雜度

SPFA 平均 O(m)，A* 搜索狀態數遠小於暴力，通常能快速找到第 k 短路。