poj2449 Remmarguts' Date【A*算法】

转载请注明出处，谢谢：http://www.cnblogs.com/KirisameMarisa/p/4303855.html ---by 墨染之樱花

【题目描述】：给出图，求从起点到终点的第K短路

【思路】：求第K短的算法基于BFS搜索，当终点出队K次时，所走的总距离就是第K短路，不过这样那些不该走的路会被反复的走，造成许多空间时间浪费，这时候就要用到启发式的A*搜索。关于此算法的详细内容请自行查阅资料，这里简单的提一下。A*算法利用一个估价函数f(n)=g(n)+h(n)，其中g(n)表示起点s到点n所耗费的实际代价，h(n)表示n到终点t所估计的代价，也就是说理想情况下从n到t还要耗费的代价，h(n)越接近真实值算法速度越快（实际上BFS就是h(n)始终为0的A*特例）。在网格图中h(n)可以为欧几里得距离或者是曼哈顿距离，在此题中，我们将从n到t的最短路作为h(n)。完成估价函数以后，我们以估价函数为优先级进行搜索（可以用优先队列实现，f(n)小的先搜索），这样就能大致保证搜索路径始终朝着我们想要的方向走，从而加快搜索速度。

  1 #include <iostream>
  2 #include <ios>
  3 #include <iomanip>
  4 #include <functional>
  5 #include <algorithm>
  6 #include <vector>
  7 #include <sstream>
  8 #include <list>
  9 #include <queue>
 10 #include <deque>
 11 #include <stack>
 12 #include <string>
 13 #include <set>
 14 #include <map>
 15 #include <cstdio>
 16 #include <cstdlib>
 17 #include <cctype>
 18 #include <cmath>
 19 #include <cstring>
 20 #include <climits>
 21 using namespace std;
 22 #define XINF INT_MAX
 23 #define INF 1<<30
 24 #define MAXN 1000+10
 25 #define eps 1e-10
 26 #define zero(a) fabs(a)<eps
 27 #define sqr(a) ((a)*(a))
 28 #define MP(X,Y) make_pair(X,Y)
 29 #define PB(X) push_back(X)
 30 #define PF(X) push_front(X)
 31 #define REP(X,N) for(int X=0;X<N;X++)
 32 #define REP2(X,L,R) for(int X=L;X<=R;X++)
 33 #define DEP(X,R,L) for(int X=R;X>=L;X--)
 34 #define CLR(A,X) memset(A,X,sizeof(A))
 35 #define IT iterator
 36 #define PI  acos(-1.0)
 37 #define test puts("OK");
 38 #define _ ios_base::sync_with_stdio(0);cin.tie(0);
 39 typedef long long ll;
 40 typedef pair<int,int> PII;
 41 typedef priority_queue<int,vector<int>,greater<int> > PQI;
 42 typedef vector<PII> VII;
 43 typedef vector<int> VI;
 44 #define X first
 45 #define Y second
 46 
 47 int V,E,S,T,K;
 48 int d[MAXN];
 49 VII G[MAXN];
 50 VII rG[MAXN];   //对反图dijkstra，求出每个点到终点的最短路，作为预计代价h(n) 
 51 int cnt[MAXN]={0};   //记录出队次数 
 52 
 53 void dijkstra(int s)
 54 {
 55     priority_queue<PII,VII,greater<PII> > Q;
 56     fill(d,d+V,INF);
 57     d[s]=0;
 58     Q.push(MP(d[s],s));
 59     while(!Q.empty())
 60     {
 61         PII p=Q.top();Q.pop();
 62         int v=p.Y;
 63         if(d[v]<p.X)
 64             continue;
 65         REP(i,rG[v].size())
 66         {
 67             PII e=rG[v][i];
 68             if(d[e.X]>d[v]+e.Y)
 69             {
 70                 d[e.X]=d[v]+e.Y;
 71                 Q.push(MP(d[e.X],e.X));
 72             }
 73         }    
 74     }
 75 }
 76 
 77 struct node    //A*搜索用节点 
 78 {
 79     int num,g,h;
 80     bool operator<(const node &b)const
 81     {
 82         return g+h!=b.g+b.h?g+h>b.g+b.h:g>b.g;   //以f=g+h为第一关键字，g为第二关键字 
 83     }
 84     node(int _num=0,int _g=0,int _h=0){num=_num;g=_g;h=_h;}
 85 };
 86 
 87 int astar(int s,int t)
 88 {
 89     priority_queue<node> Q;
 90     node st(s,0,d[s]);
 91     Q.push(st);
 92     while(!Q.empty())
 93     {
 94         node temp=Q.top();Q.pop();
 95         int u=temp.num,ug=temp.g,uh=temp.h;
 96         cnt[u]++;
 97         if(u==t && cnt[t]==K)
 98             return ug;
 99         if(cnt[u]>K)
100             continue;
101         REP(i,G[u].size())
102         {
103             int v=G[u][i].X,cost=G[u][i].Y;
104             node next(v,ug+cost,d[v]);
105             Q.push(next);
106         }
107     }
108     return -1;
109 }
110 
111 int main()
112 {_
113     scanf("%d%d",&V,&E);
114     REP(i,E)
115     {
116         int x,y,c;
117         scanf("%d%d%d",&x,&y,&c);
118         x--;y--;
119         G[x].PB(MP(y,c));
120         rG[y].PB(MP(x,c));
121     }
122     scanf("%d%d%d",&S,&T,&K);
123     S--;T--;
124     if(S==T)   //起点与终点相同时，最短路显然是0，不过不能算 ，所以k++ 
125         K++;
126     dijkstra(T);   //反向dijkstra，求出每个点到T的最短路，作为h(i) 
127     printf("%d
",astar(S,T));
128     return 0;
129 }

View Code