POJ2449 K短路

SPFA + A*

先计算反向图T为源点的最短路dis[]。再做A*, 状态h值为dis[X]， g值便是走过的路径长度和， 第K次出的解即为所求最短路。

注意A*时不能有一般的最优剪枝，因为所求的是第K次出的解，剪枝会引起错误。

代码：

#include <iostream>
#include <queue>
#include <stdio.h>

using namespace std;

#define     INF     1000000000

struct Node{
    Node(int a, int b):u(a),v(b),next(0){}
    int u, v, cost;
    Node *next;
};

struct State{
    int pos;
    int g, h;
    friend bool operator < (State a, State b){
        return a.h+a.g > b.h+b.g;
    }
};

Node*   E[1001] = {0};
Node*   E2[1001] = {0};
int     S, T, K, N, M;
int     dis[1001];

void AddEdge(int u, int v, int cost){
    Node* x = new Node(u, v);
    x->cost = cost;
    x->next = E[u];
    E[u] = x;
}
void AddEdge2(int u, int v, int cost){
    Node* x = new Node(u, v);
    x->cost = cost;
    x->next = E2[u];
    E2[u] = x;
}

void spfa(int s, int t){
    int inq[1001] = {0};
    queue<int> q;

    for (int i=1; i<=N; i++)
        dis[i] = (i == s) ? 0 : INF;
    inq[s] = 1;
    q.push(s);

    while (!q.empty()){
        int u = q.front(); q.pop();
        inq[u]= 0;
        for (Node *e=E2[u]; e!=NULL; e=e->next){
            int v = e->v;
            if (dis[v] > dis[u] + e->cost){
                dis[v] = dis[u] + e->cost;
                if (!inq[v]){
                    inq[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

int AStar(int s, int t, int k){
    int vis[1001] = {0};
    priority_queue<State> q;

    State beg;
    beg.pos = s;
    beg.g   = 0;
    beg.h   = dis[s];

    q.push(beg);
    while (!q.empty()){
        State u = q.top(); q.pop();
        vis[u.pos]++;
        if (vis[u.pos]==k && u.pos==t)
            return u.g + u.h;
        if (vis[u.pos] > k) continue;
        // expand u
        for (Node *e=E[u.pos]; e!=0; e=e->next){
            State ns;
            ns.g = u.g + e->cost;
            ns.h = dis[e->v];
            ns.pos = e->v;
            q.push(ns);
        }
    }

    return -1;
}

int main()
{
    cin>>N>>M;
    for (int i=0; i<M; i++){
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        AddEdge(a, b, c);
        AddEdge2(b, a, c);
    }

    cin>>S>>T>>K;
    if (S == T) K++;
    spfa(T, S);

    cout<<AStar(S, T, K)<<endl;

    return 0;
}