http://poj.org/problem?id=2449

A*搜索求K短路。

?

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <set> #include <map> #include <cmath> #include <queue> using namespace std; template <class T> void checkmin(T &t,T x) {if(x < t) t = x;} template <class T> void checkmax(T &t,T x) {if(x > t) t = x;} template <class T> void _checkmin(T &t,T x) {if(t==-1) t = x; if(x < t) t = x;} template <class T> void _checkmax(T &t,T x) {if(t==-1) t = x; if(x > t) t = x;} typedef pair <int,int> PII; typedef pair <double,double> PDD; typedef long long ll; #define foreach(it,v) for(__typeof((v).begin()) it = (v).begin(); it != (v).end ; it ++) const int N = 1001; #define inf (1<<29) struct nod{int x,val;nod() {}friend bool operator < (const nod& a,const nod& b){return b.val<a.val;} }; vector<struct nod> g[N],r[N]; priority_queue<nod,vector<nod> > Q; int n,m,S,T,K,dist[N],out[N],size; void dijkstra(){bool vi[N];vector<struct nod>::iterator iter;for(int i=1;i<=n;i++){vi[i]=0;dist[i]=inf;}dist[T]=0;while(1){int k=-1;for(int i=1;i<=n;i++)if(!vi[i] && (k==-1 || dist[i]<dist[k])) k=i;if(k==-1) break;vi[k]=1;vector<struct nod>::iterator iter;for(iter=r[k].begin();iter!=r[k].end();iter++)if(!vi[(*iter).x] && dist[(*iter).x]>dist[k]+(*iter).val)dist[(*iter).x]=dist[k]+(*iter).val;} } int astar(){dijkstra();nod v;v.x=S;v.val=dist[S];Q.push(v);vector<struct nod>::iterator iter;for(int i=0;i<=n;i++) out[i]=0;while(!Q.empty() && out[T]<K){v=Q.top();Q.pop();if(out[v.x]>=K) continue;if(v.x==T){out[v.x]++;if(v.x==T && out[v.x]==K) return v.val;}for(iter=g[v.x].begin();iter!=g[v.x].end();iter++){if(out[(*iter).x]>=K) continue;nod tmp;tmp.val=v.val-dist[v.x]+(*iter).val+dist[(*iter).x];tmp.x=(*iter).x;Q.push(tmp);}}return -1; } int main(){while(~scanf("%d%d",&n,&m)){int a,b,w;for(int i=1;i<=n;i++) { g[i].clear();r[i].clear(); }while(m--){scanf("%d%d%d",&a,&b,&w);nod tmp;tmp.x=b;tmp.val=w;g[a].push_back(tmp);tmp.x=a;r[b].push_back(tmp);}scanf("%d%d%d",&S,&T,&K);if(S==T) K++;int ans=astar();printf("%d\n",ans);}return 0; }

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/aiiYuu/archive/2013/04/01/2993815.html

總結(jié)

以上是生活随笔為你收集整理的Poj2449 Remmarguts' Date 【A*搜索】K短路的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。