POJ 2449 Remmarguts' Date 第K短路 A* + SPFA

題目大意就是給出一個圖，然後給出一個起點個一個終點，求這兩點間的第K短路。

本題中是可以走重複的路的，是以如果一張圖中有一個環的話，無論求第幾短路都是存在的。

網上大部分的方法都是用A* + 最短路的方法做的。  

對于A* ，估價函數 = 目前值+目前位置到終點的距離，即 F（p）=g（p）+h（p），每次擴充估價函數值中最小的一個。對于k短路來說，g（p）為目前從s到p所走的長度，h（p）為從p到 t 的最短路的長度，則F（p）的意義就是從s按照目前路徑走到 p 後要走到終點 t 一共至少要走多遠。也就是說我們每次的擴充都是有方向的擴充，這樣就可以提高求解速度和降低擴充的狀态數目。為了加速計算，h（p）需要從A*搜尋之前進行預處理，隻要将原圖的所有邊反向，再從終點 t 做一次單源最短路徑就可以得到每個點的h（p）了。

在下面這個代碼中

A結構體中，v代表的是目前走到的點，f和g分别為f函數和g函數的值，每次優先搜的是f函數較小的。這樣就能保證搜尋出來的一定是第K小短路，并且避免了一定的不必要計算。

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#define MAXN 1005
#define MAXM 500005
#define INF 1000000000
using namespace std;
struct node
{
    int v, w, next;
}edge[MAXM], revedge[MAXM];
struct A
{
    int f, g, v;
    bool operator <(const A a)const {
        if(a.f == f) return a.g < g;
        return a.f < f;
    }
};
int e, vis[MAXN], d[MAXN], q[MAXM * 5];
int head[MAXN], revhead[MAXN];
int n, m, s, t, k;
void init()
{
    e = 0;
    memset(head, -1, sizeof(head));
    memset(revhead, -1, sizeof(revhead));
}
void insert(int x, int y, int w)
{
    edge[e].v = y;
    edge[e].w = w;
    edge[e].next = head[x];
    head[x] = e;
    revedge[e].v = x;
    revedge[e].w = w;
    revedge[e].next =revhead[y];
    revhead[y] = e++;
}
void spfa(int src)
{
    for(int i = 1; i <= n; i++) d[i] = INF;
    memset(vis, 0, sizeof(vis));
    vis[src] = 0;
    int h = 0, t = 1;
    q[0] = src;
    d[src] = 0;
    while(h < t)
    {
        int u = q[h++];
        vis[u] = 0;
        for(int i = revhead[u] ; i != -1; i = revedge[i].next)
        {
            int v = revedge[i].v;
            int w = revedge[i].w;
            if(d[v] > d[u] + w)
            {
                d[v] = d[u] + w;
                if(!vis[v])
                {
                    q[t++] = v;
                    vis[v] = 1;
                }
            }
        }
    }
}
int Astar(int src, int des)
{
    int cnt = 0;
    priority_queue<A>Q;
    if(src == des) k++;
    if(d[src] == INF) return -1;
    A t, tt;
    t.v = src, t.g = 0, t.f = t.g + d[src];
    Q.push(t);
    while(!Q.empty())
    {
        tt = Q.top();
        Q.pop();
        if(tt.v == des)
        {
            cnt++;
            if(cnt == k) return tt.g;
        }
        for(int i = head[tt.v]; i != -1; i = edge[i].next)
        {
            t.v = edge[i].v;
            t.g = tt.g + edge[i].w;
            t.f = t.g + d[t.v];
            Q.push(t);
        }
    }
    return -1;
}
int main()
{
    int x, y, w;
    while(scanf("%d%d", &n, &m) != EOF)
    {
        init();
        for(int i = 1; i <= m; i++)
        {
            scanf("%d%d%d", &x, &y, &w);
            insert(x, y, w);
        }
        scanf("%d%d%d", &s, &t, &k);
        spfa(t);
        printf("%d\n", Astar(s, t));
    }
    return 0;
}