本文主要是介绍poj2449 Remmarguts' Date --- k短路模板（SPFA+A*），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给一个图，起点s、终点t、k，求起点到终点的第k短路。
基本思路：
首先反向图中求出终点 t 到其他所有点的距离（预处理优化），
再从起点开始使用优先队列进行宽搜，用cnt记录到达终点的次数，当cnt==k时的路径长度即为所得。
搜索的方向用一个估价函数 f=g+h 来确定，其中g表示到当前点的路径长度，h表示当前点到终点的最短路径，即之前的预处理。
A*算法结合了启发式搜索（充分利用题目所给信息来动态的做出决定，使搜索次数大大降低），和形式化方法（不利用图给出的信息，仅利用数学的形式分析，如dij算法）。
它通过一个估价函数 f(h) 来决定搜索方向。估价函数=当前值+当前位置到终点的距离，每次扩展估价函数值最小的一个。
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#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+hbool operator < (const node1 &r) const{if(r.f==f) return r.g<g;return r.f<f;}
};void init()
{memset(head,-1,sizeof head);memset(head2,-1,sizeof head2);memset(d,0x3f,sizeof d);h=0;
}void addedge(int u,int v,int w)
{e[h].v=v;e[h].w=w;e[h].next=head[u];head[u]=h;e2[h].v=u;//反向存图 找从终点到其他点的最短路径e2[h].w=w;e2[h].next=head2[v];head2[v]=h++;
}bool spfa(int s)
{memset(vis,0,sizeof vis);queue<int> 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<d[e2[i].v]){d[e2[i].v]=d[now]+e2[i].w;if(!vis[e2[i].v]){vis[e2[i].v]=1;q.push(e2[i].v);}}}}
}int astar(int s,int t,int k)
{if(s==t) k++;//起点=终点 则最短路为0 要注意哦if(d[s]==inf) return -1;priority_queue<node1> 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<m;i++){scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}scanf("%d%d%d",&s,&t,&k);spfa(t);int ans=astar(s,t,k);printf("%d\n",ans);}return 0;
}
这篇关于poj2449 Remmarguts' Date --- k短路模板（SPFA+A*）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
