POJ2449 Remmarguts' Date 第K短路

K短路求法：SPFA+A*。

简单讲讲这个A*算法。它有一个估价函数 f(x) ， 定义f(x) = g(x) + h(x). 其中g(x)为从起点到当前点的代价， h(x)为从当前点到终点的代价。

怎么把它用来求K短路呢？

定义结构体Node，其中有成员（to, f, g），to为当前顶点，f , g和上面定义相同。

在求K短路中g(x)就是重源点到当前点的路径长度，h(x)的就是当前点到终点的距离。

g(x)好求，我理解就是用的优先队列的diskstra（不完全一样，这里优先队列的优先权以结构体Node的成员f为准）。

h(x)需要求当前点到终点的距离，直接求不太好求。所以我们求终点到当前点的距离，这两者等价。把所有给定的边反向，值不变，然后用一次SPFA或者diskstra就可以求出来了。

把源点放入优先队列一直搜索，直到终点出现次数为k时返回，如果搜索完了还没有返回，则回返-1。

需要注意的一点是，如果源点和终点相同，那么需要搜索k+1次，因为第一次出队的时候肯定是源点，而这个时候源点一条边也没有经过就到达了终点，显然不能算数。

同时，如果源点是终点不可达的，那么不存在K短路。

K短路的模板题，但还是MLE了好久。主要是A*写错了。由于用到了优先队列，所以尽管数组开的大小是不超内存的，但是在执行A*的过程可能超内存。

代码：

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

using namespace std;

const int N = 1024;
const int M = 100008;
const int INF = 0x3f3f3f3f;

int n, m;

struct Edge {
    int v, w;
    int next;
};

int fir[N];
int revFir[N];
Edge edge[M];
Edge revEdge[M];
int cnt1, cnt2;

void init() {
    cnt1 = 1;
    cnt2 = 1;
    memset(fir, -1, sizeof(fir));
    memset(revFir, -1, sizeof(revFir));
}

void addEdge(int u, int v, int w) {
    edge[cnt1].v = v;
    edge[cnt1].w = w;
    edge[cnt1].next = fir[u];
    fir[u] = cnt1++;

    revEdge[cnt2].v = u;
    revEdge[cnt2].w = w;
    revEdge[cnt2].next = revFir[v];
    revFir[v] = cnt2++;
}

struct Node {
    int to;
    int f, g;
    bool operator <(const Node &other)const {
        if(other.f == f) return other.g < g;
        return other.f < f;
    }
};

int dis[N], vis[N];

bool SPFA(int s) {
    queue<int> que;
    memset(dis, INF, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[s] = 0;
    que.push(s);
    while(!que.empty()) {
        int cur = que.front();
        que.pop();
        vis[cur] = 0;
        for(int i = revFir[cur]; i != -1; i = revEdge[i].next) {
            int v = revEdge[i].v;
            if(dis[v] > dis[cur] + revEdge[i].w) {
                dis[v] = dis[cur] + revEdge[i].w;
                if(!vis[v]) {
                    vis[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    return true;
}

int AStar(int s, int t, int k) {

    if(s == t) k++;
    if(dis[s] == INF) return -1;
    priority_queue<Node> pque;
    Node cur, fwd;
    cur.to = s;
    cur.g = 0;
    cur.f = cur.g + dis[s];
    pque.push(cur);
    int cnt = 0;
    while(!pque.empty()) {
        cur = pque.top();
        pque.pop();
        if(cur.to == t) cnt++;
        if(cnt == k)
            return cur.g;
        for(int i = fir[cur.to]; i != -1; i = edge[i].next) {
            fwd.to = edge[i].v;
            fwd.g = cur.g + edge[i].w;
            fwd.f = fwd.g + dis[fwd.to];
            pque.push(fwd);
        }
    }
    return -1;
}


int main() {

    while(~scanf("%d%d", &n, &m)) {
        init();
        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;
}