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

/* k短路问题 spfa+A* A*算法入门 http://www.cppblog.com/mythit/archive/2009/04/19/80492.aspx 初识A*算法 http://tekbots.eefocus.com/article/10-01/1688061264487401.html A*算法就是通过估价函数(f[x]=g[x]+h[x])优先选择更接近目标的节点进行搜索 再来说第k次到达t就是到t的k短路：A*其实是一个优化，主要算法还是一个广搜，捡着较近的路走， 第一次肯定时最短的，然后因为是广搜，不会再最短的，所以第二次到达是第二短的，所以， 第k次到达就是第k短了 在本题中 g[x]是s到x的实际距离， h[x]是x到t的估计代价，这个可以通过求各点到t的最短路得到 */ #include<stdio.h> #include<queue> using namespace std; int n,m,k,s,t; struct edge//存储边 { int yong; int head[1005]; int v[100005]; int next[100005]; int w[100005]; void clear() { yong=1; memset(head,0,sizeof(head)); } void add(int a,int b,int c) { v[yong]=b; w[yong]=c; next[yong]=head[a]; head[a]=yong; yong++; } }e,e2;//正向边和反向边 int dist[1005],vis[1005],cnt[1005]; struct node//A*的时候用到的优先队列节点 { int v,g,h;//节点号 估价函数里边的那两项 friend bool operator<(node a,node b) { return a.g+a.h>b.g+b.h; } }; void spfa()//求逆向最短路 { int i,j,u,v; queue<int>q; for(i=0;i<=n;++i) dist[i]=0x7fffffff; memset(vis,0,sizeof(vis)); vis[t]=1; dist[t]=0; q.push(t); while(!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for(j=e2.head[u];j;j=e2.next[j]) { v=e2.v[j]; if(dist[v]>dist[u]+e2.w[j]) { dist[v]=dist[u]+e2.w[j]; if(!vis[v]) { vis[v]=1; q.push(v); } } } } } int a_star()//A* { if(s==t) ++k; if(dist[s]==0x7fffffff) return -1; memset(cnt,0,sizeof(cnt)); priority_queue<node>q; node nod,no; nod.v=s; nod.g=0; nod.h=dist[s]; q.push(nod); while(!q.empty()) { nod=q.top(); q.pop(); cnt[nod.v]++; if(cnt[t]==k) return nod.g;//找到则返回长度 if(cnt[nod.v]>k) continue;//对任意一个节点来说 只需求它的k短路 //若不是目标路径上的节点，那就没什么说的了；若是，也只需要k短，这里的k短就可以造成t产生k短 for(int i=e.head[nod.v];i;i=e.next[i]) { no.v=e.v[i]; no.g=nod.g+e.w[i]; no.h=dist[no.v]; q.push(no); } } return -1; } int main() { int i,a,b,c; while(scanf("%d%d",&n,&m)!=EOF) { e.clear(); e2.clear(); for(i=1;i<=m;++i) { scanf("%d%d%d",&a,&b,&c); e.add(a,b,c); e2.add(b,a,c); } scanf("%d%d%d",&s,&t,&k); spfa(); printf("%d\n",a_star()); } return 0; }