POJ2449 Remmarguts' Date(k短路(A*优化))

POJ2449 Remmarguts’ Date

题意：

有n个节点，m条边，求任意两点间的第k短路径长度

分析：

对Astar算法不熟可以移步大佬博客：https://blog.csdn.net/hitwhylz/article/details/23089415
讲得很详细，但比较长
我下面的代码中有对A*的简单注释，可自行参考

常规的k短路板子题
但是由于本蒟蒻有一段时间没写图论题了，wa了几发…
有几个需要注意的地方：

• 输入的边是有向边，我开始当作无向边做了。。。
• 当询问s到s的第k短路时需要特殊考虑，因为我们设置自身到自身的最短路长是0，然而图中并没有自环，所以实际上并不存在长为0的这条路径，需要排除这种情况。
• 还有一点，必须要吐槽一波poj，万能头不能用就算了，连vector<pair<int,int>> ve两个’>'连在一起都编译失败。。。我本地编译得好好的呢

代码：

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

const int maxn = 1010;
const int inf = 0x3f3f3f3f;
int n, m, k;
struct Node
{
    int f, g, v;
    bool operator<(const Node &a) const
    {
        if (f == a.f)
            return g > a.g;
        return f > a.f;
    }
};

vector<pair<int, int> > ve1[maxn], ve2[maxn];
int inq[maxn];
int dis[maxn];

void spfa(int st)
{
    memset(inq, 0, sizeof inq);
    memset(dis, inf, sizeof dis);
    queue<int> q;
    q.push(st);
    inq[st] = 1, dis[st] = 0;
    while (!q.empty())
    {
        int now = q.front();
        q.pop(), inq[now] = 0;
        for (int i = 0; i < ve2[now].size(); ++i)
        {
            int v = ve2[now][i].first;
            if (dis[v] > dis[now] + ve2[now][i].second)
            {
                dis[v] = dis[now] + ve2[now][i].second;
                if (inq[v])
                    continue;
                inq[v] = 1;
                q.push(v);
            }
        }
    }
}

//上面的spfa求出了从终点到其余各点的最短路径（单源最短路）dis[]，下面的A*实则是一个优化版的BFS，普通BFS搜索是盲目的，
//而A*就是借助dis[]数组来预测最短路，从而优化搜索时间
int Astar(int src, int des)
{
    int cnt = 0;
    priority_queue<Node> q;	//使队列中与终点的预测距离最近的位于队首
    if (src == des)         //因为src=des时第一短路是0，需要排除，所以k++
        k++;
    if (dis[src] == inf)
        return -1;
    Node x, y;
    x.v = src;
    x.g = 0;
    x.f = x.g + dis[x.v];
    q.push(x);
    while (!q.empty())
    {
        y = q.top();
        q.pop();
        if (y.v == des)
        {
            ++cnt;
            if (cnt == k)
                return y.g;
        }
        for (int i = 0; i < ve1[y.v].size(); ++i)
        {
            x.v = ve1[y.v][i].first;
            x.g = ve1[y.v][i].second + y.g;
            x.f = x.g + dis[x.v];
            q.push(x);
        }
    }
    return -1;
}

int main(int argc, char const *argv[])
{
    int x, y, z;
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; ++i)
            ve1[i].clear(), ve2[i].clear();
        for (int i = 1; i <= m; ++i)
        {
            scanf("%d%d%d", &x, &y, &z);
            ve1[x].push_back(make_pair(y, z));
            ve2[y].push_back(make_pair(x, z));
        }
        scanf("%d%d%d", &x, &y, &k);
        spfa(y);
        printf("%d\n", Astar(x, y));
    }
    return 0;
}