POJ 2449 K短路 A*搜索

题目链接

---

题意： 求一个有向图的$k$短路长度。

---

思路： 经典问题的经典算法——$A\ast$搜索。 感觉$A\ast$搜索和$Dijkstra$堆优化写法有很多类似的地方。

首先以每个点到终点的最短距离作为估计函数$g$，故先需要反向建图，随后对反图从终点$T$做一遍$Dijkstra$。

随后从起点开始$A\ast$搜索，第$k$个搜索到的值即为第$k$短路长度。

另外注意当$S==T$时，$k$需要加$1$，因为必须经过至少一条路径。

此题得解。

---

代码：

#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<queue> using namespace std; typedef long long ll; const int INF = 1e8 + 10; const int A = 2e3 + 10; const int B = 2e5 + 10; class Gra{ public: int v,w,next; }G[B]; class Gra_Inv{ public: int v,w,next; }IG[B]; int n,m,S,T,K; int head[A],Ihead[A],g[A],dis[A],tot,Itot; bool vis[A]; class P{ public: int id,W; P(int _id = 0,int _w = 0){ id = _id; W = _w; } bool operator<(const P& rhs)const{ return W+g[id] > rhs.W+g[rhs.id]; } }; priority_queue<P> que; void init(){ memset(head,-1,sizeof(head)); memset(Ihead,-1,sizeof(Ihead)); memset(g,0,sizeof(g)); tot = Itot = 0; } void add(int u,int v,int w){ G[tot].v = v; G[tot].w = w; G[tot].next = head[u]; head[u] = tot++; } void Iadd(int u,int v,int w){ IG[Itot].v = v; IG[Itot].w = w; IG[Itot].next = Ihead[u]; Ihead[u] = Itot++; } void Dijkstra(int st){ while(que.size()) que.pop(); for(int i=0 ;i<=n ;i++){ dis[i] = INF; vis[i] = 0; } que.push(P(st,0)); dis[st] = 0; while(que.size()){ P x = que.top();que.pop(); int u = x.id; if(vis[u]) continue; vis[u] = 1; for(int i=Ihead[u] ;i!=-1 ;i=IG[i].next){ int v = IG[i].v,w = IG[i].w; if(dis[v] > dis[u] + w){ dis[v] = dis[u] + w; que.push(P(v,dis[v])); } } } for(int i=1 ;i<=n ;i++){ g[i] = dis[i]; } } int a_star(int st){ while(que.size()) que.pop(); que.push(P(st,0)); int cnt = 0; while(que.size()){ P x = que.top();que.pop(); int u = x.id; if(u == T){ cnt++; if(cnt == K) return x.W; } for(int i=head[u] ;i!=-1 ;i=G[i].next){ que.push(P(G[i].v,G[i].w + x.W)); } } return -1; } int main(){ scanf("%d%d",&n,&m); init(); for(int i=1 ;i<=m ;i++){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add(u,v,w);Iadd(v,u,w); } scanf("%d%d%d",&S,&T,&K); if(S == T) K++; Dijkstra(T); printf("%d\n",a_star(S)); return 0; }