程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2449 Remmarguts&#39; Date --- k短路模板（SPFA+A*）

poj2449 Remmarguts&#39; Date --- k短路模板（SPFA+A*）

編輯：C++入門知識

給一個圖，起點s、終點t、k，求起點到終點的第k短路。

基本思路：

首先反向圖中求出終點 t 到其他所有點的距離（預處理優化），

再從起點開始使用優先隊列進行寬搜，用cnt記錄到達終點的次數，當cnt==k時的路徑長度即為所得。

搜索的方向用一個估價函數 f=g+h 來確定，其中g表示到當前點的路徑長度，h表示當前點到終點的最短路徑，即之前的預處理。

A*算法結合了啟發式搜索（充分利用題目所給信息來動態的做出決定，使搜索次數大大降低），和形式化方法（不利用圖給出的信息，僅利用數學的形式分析，如dij算法）。

它通過一個估價函數 f(h) 來決定搜索方向。估價函數=當前值+當前位置到終點的距離，每次擴展估價函數值最小的一個。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define inf 0x3f3f3f3f
#define ll long long
#define mod 1000000007
using namespace std;

const int maxn=1010;

int d[maxn],head[maxn],head2[maxn],n,m,h;
bool vis[maxn];

struct node
{
    int v,w,next;
}e[100010],e2[100010];

struct node1
{
    int v,g,f;// f=g+h
    bool operator < (const node1 &r) const
    {
        if(r.f==f) return r.g q;
    d[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int now=q.front();
        q.pop();
        vis[now]=0;
        for(int i=head2[now];i!=-1;i=e2[i].next)
        {
            if(d[now]+e2[i].w q;
    int cnt=0;
    node1 tmp,to;
    tmp.v=s;
    tmp.g=0;
    tmp.f=tmp.g+d[tmp.v];
    q.push(tmp);
    while(!q.empty())
    {
        tmp=q.top();
        q.pop();
        if(tmp.v==t) cnt++;
        if(cnt==k) return tmp.g;
        for(int i=head[tmp.v];i!=-1;i=e[i].next)
        {
            to.v=e[i].v;
            to.g=tmp.g+e[i].w;
            to.f=to.g+d[to.v];
            q.push(to);
        }
    }
    return -1;
}

int main()
{
    int u,v,w,s,t,k;
    while(~scanf("%d%d",&n,&m))
    {
        init();
        for(int i=0;i