POJ 2449：Remmarguts' Date（A* + SPFA）

题目链接

题意

给出n个点m条有向边，源点s，汇点t，k。问s到t的第k短路的路径长度是多少，不存在输出-1.

思路

A*算法是启发式搜索，通过一个估价函数 f(p) = g(p) + h(p) ，其中源点到p的距离是g(p)，从p到汇点的距离是h(p)，从源点经过p点到达汇点的长度f(p)，来决定搜索的方向。

因此反向建图，从汇点出发处理出h数组，然后就可以用A*来做了。用优先队列，每次出队的点为t的话，就cnt++，当cntk的时候，就说明是第k短路了。

注意一开始st的情况，因为要跑出路径，所以要k++。

#include <cstdio>

#include <cstdlib>

#include <queue>

#include <cstring>

using namespace std;

const int N = 1011;

const int M = 100011;

const int INF = 0x3f3f3f3f;

struct Edge {

    int v, nxt, w;

} edge[M];

struct Node {

    int u, g, h;

    friend bool operator < (const Node &a, const Node &b) {

        return a.g + a.h > b.h + b.g;

    }

};

int n, m, h[N], vis[N], s, t, k, U[M], V[M], W[M], head[N], tot;

void Add(int u, int v, int w) {

    edge[tot] = (Edge) { v, head[u], w }; head[u] = tot++;

}

void Spfa() {

    memset(h, INF, sizeof(h));

    memset(vis, 0, sizeof(vis));

    queue<int> que; que.push(t);

    vis[t] = 1; h[t] = 0;

    while(!que.empty()) {

        int u = que.front(); que.pop();

        vis[u] = 0;

        for(int i = head[u]; ~i; i = edge[i].nxt) {

            int v = edge[i].v, w = edge[i].w;

            if(h[v] > h[u] + w) {

                h[v] = h[u] + w;

                if(!vis[v]) vis[v] = 1, que.push(v);

            }

        }

    }

}

int Astar() {

    if(h[s] == INF) return -1;

    if(s == t) k++;

    Node now = (Node) { s, 0, h[s] };

    priority_queue<Node> que; que.push(now);

    int cnt = 0;

    while(!que.empty()) {

        now = que.top(); que.pop();

        int u = now.u, gg = now.g, hh = now.h;

//        printf("%d : %d - %d\n", u, gg, hh);

        if(u == t) cnt++;

        if(cnt == k) return gg + hh;

        for(int i = head[u]; ~i; i = edge[i].nxt) {

            int v = edge[i].v, w = edge[i].w;

            now = (Node) { v, gg + w, h[v] };

            que.push(now);

        }

    }

    return -1;

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        memset(head, -1, sizeof(head)); tot = 0;

        for(int i = 1; i <= m; i++) {

            scanf("%d%d%d", &U[i], &V[i], &W[i]);

            Add(V[i], U[i], W[i]);

        }

        scanf("%d%d%d", &s, &t, &k);

        Spfa();

        memset(head, -1, sizeof(head)); tot = 0;

        for(int i = 1; i <= m; i++)

            Add(U[i], V[i], W[i]);

        printf("%d\n", Astar());

    }

    return 0;

}