POJ 2449 K短路（Dijkstra + A*搜索）

题目大意：

　　给定一个有向图，求st到ed的第k短路。

分析：

　　显然，我是看解题报告的。

　　1、逆向求所有点到ed的最短距离（Dijkstra，ed作为起始点）;

　　2、A*，即建立一个优先级f[x]= h[x] + g[x]; h[x]作为当前搜索时的代价（即本题搜索中的实际距离），g[x]为估价函数，从当前节点移动到目标节点的预估费用，本题选1中所求的最短距离作为估价函数g，进行普通的bfs+优先队列就可以了，用cnt[]记录每个点出队列的次数，当cnt[u]>k就可以continue; 当cnt[u]==k && u==ed 说明得解，h[u]即是答案。

　　http://blog.csdn.net/kk303/article/details/6953943

关于A*算法：http://www.cppblog.com/mythit/archive/2012/06/23/80492.html

　　　　　　http://www.java3z.com/cwbwebhome/article/article2/2825.html

PS：这题有重边，重边的Dijkstra应该是按我这样子写的吧; 这题如果st == ed ，网上都说要 k++;

代码：

poj2449

 1 /*2449    Accepted    11368K    485MS    C++    2492B    2012-06-26 13:38:15*/
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <iostream>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 using namespace std;
10 
11 #define mpair make_pair
12 #define pii pair<int,int>
13 #define MM(a,b) memset(a,b,sizeof(a));
14 typedef long long lld;
15 typedef unsigned long long u64;
16 template<class T> bool up_max(T& a,const T& b){return b>a? a=b,1 : 0;}
17 template<class T> bool up_min(T& a,const T& b){return b<a? a=b,1 : 0;}
18 #define maxn 1005
19 const int inf= 2100000000;
20 
21 int n,m;
22 vector< pii > e[maxn], e2[maxn];
23 
24 int dis[maxn];
25 bool vis[maxn];
26 void Dijkstra(int st){
27     for(int i=1;i<=n;++i) dis[i]= inf, vis[i]= 0;
28     dis[st]= 0,  vis[st]= 1;
29     for(int i=0;i<e2[st].size();++i)
30         up_min( dis[ e2[st][i].first ], e2[st][i].second );
31 
32     while(1){
33         int mdis= inf, idx= -1;
34         for(int i=1;i<=n;++i){
35             if( !vis[i] && up_min( mdis, dis[i] ) )
36                 idx= i;
37         }
38         if( -1 == idx ) break;
39         vis[idx]= 1;
40         for(int i=0;i<e2[idx].size();++i){
41             int v= e2[idx][i].first, w= e2[idx][i].second;
42             if( !vis[v] )
43                 up_min( dis[v], dis[idx] + w );
44         }
45     }
46 }
47 
48 struct Node{
49     int u, h, g; /// h[u]+g[u];
50     Node(int u_,int h_,int g_){u=u_,h=h_,g=g_;}
51     bool operator<(Node a)const{
52         return h+g > a.h+a.g;
53     }
54 };
55 priority_queue<Node>Q;
56 
57 int cnt[maxn];
58 int Astar(int st, int ed, int k){ /// A*: return the k-th shortest path from st to ed;
59     while( !Q.empty() ) Q.pop();
60     fill( cnt, cnt+1+n, 0 );
61     Q.push( Node( st, 0, dis[st] ) );
62 
63     while( !Q.empty() ){
64         Node a= Q.top(); Q.pop();
65         int u= a.u, h= a.h, g= a.g;
66         ++cnt[u];
67         if( cnt[u]==k && u==ed ) return h;
68         if( cnt[u]>k ) continue;
69         for(int i=0;i<e[u].size();++i){
70             int v= e[u][i].first, w= e[u][i].second;
71             Q.push( Node( v, h+w, dis[v] ) );
72         }
73     }
74     return -1;
75 }
76 
77 int main()
78 {
79     //freopen("poj2449.in","r",stdin);
80     while( cin>>n>>m ){
81         for(int i=1;i<=n;++i) e[i].clear(), e2[i].clear();
82         while(m--){
83             int u,v,w;
84             scanf("%d%d%d", &u, &v, &w);
85             e[u].push_back( pii( v, w ) );
86             e2[v].push_back( pii( u, w ) );
87         }
88 
89         int st, ed, k;
90         cin>>st>>ed>>k;
91         if( st==ed ) ++k; ///
92         Dijkstra( ed ); /// ed;
93         cout<< Astar( st, ed, k ) <<endl;
94     }
95 }

一毛原创作品，转载请注明出处。