当前位置: 代码迷 >> 综合 >> poj 2449 Remmarguts' Date A*+spfa求第k短路
  详细解决方案

poj 2449 Remmarguts' Date A*+spfa求第k短路

热度:17   发布时间:2024-01-19 05:39:50.0

题意:

经典的第k短路,A*算法的经典应用之一。

分析:

A*,已走的路程g+到终点的最短距离为启发函数,搜索过程中不判重,第k次到t节点时就求出了第k短路。

代码:

//poj 2449
//sep9
#include <iostream>
#include <queue>
using namespace std;
const int maxN=1024;
const int maxM=100024;
int n,m,s,t,k,e,ne;
int head[maxN],nhead[maxN],dis[maxN],inq[maxN];struct EDGE
{int v,w,nxt;
}edge[maxM],nedge[maxM];struct NODE
{int ids,g;bool operator < (const NODE &a) const{return g+dis[ids]>a.g+dis[a.ids];}
};void addedge(int a,int b,int c)
{edge[e].v=b,edge[e].w=c,edge[e].nxt=head[a],head[a]=e++;nedge[ne].v=a,nedge[ne].w=c,nedge[ne].nxt=nhead[b],nhead[b]=ne++;	
}void spfa()
{queue<int> q;for(int i=1;i<=n;++i)dis[i]=INT_MAX;memset(inq,0,sizeof(inq));q.push(t);inq[t]=1;dis[t]=0;while(!q.empty()){int a=q.front();q.pop();inq[a]=0;for(int i=nhead[a];i!=-1;i=nedge[i].nxt){int b=nedge[i].v,w=nedge[i].w;if(dis[a]+w<dis[b]){dis[b]=dis[a]+w;if(!inq[b])q.push(b);}}}	
}int astar()
{priority_queue<NODE> q;NODE x;x.ids=s,x.g=0;q.push(x);while(!q.empty()){x=q.top();q.pop();if(x.ids==t){if(--k==0)return x.g;}for(int i=head[x.ids];i!=-1;i=edge[i].nxt){int v=edge[i].v,w=edge[i].w;if(dis[v]==INT_MAX) continue;NODE y;y.ids=v,y.g=x.g+w;q.push(y);}}return -1;
}int main()
{scanf("%d%d",&n,&m);e=0,ne=0;memset(head,-1,sizeof(head));memset(nhead,-1,sizeof(nhead));while(m--){int a,b,c;scanf("%d%d%d",&a,&b,&c);addedge(a,b,c);}scanf("%d%d%d",&s,&t,&k);if(s==t) ++k;spfa();printf("%d",astar());return 0;	
} 


  相关解决方案