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;
}