POJ2449 k短路问题

AA^\star算法的经典应用----k短路问题。

AA^\star算法:设f(x)=g(x)+h(x)f(x)=g(x)+h(x),其中g(x)g(x)表示已花费代价,h(x)h(x)表示预估还需代价(h(x)h(x)h(x)\le h^\star(x))表示每次找到f值最小的拿出来扩展。

给定一个n点m边的有向图,求从s到t的k短路。

首先求出所有点x到t的最短路dis[x]dis[x],接下来用dis[x]dis[x]作为h(x)h(x)AA^\star ,因为 h(x)h(x)h(x)\le h^\star(x) ,所以第k次找到t就是k短路。

注意:一条路径至少有一条边,所以当s=t的时候第一次找到的路径不是真正的路径(因为一步都没走),也就是k要+1

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
Author: CNYALI_LK
LANG: C++
PROG: poj2449.cpp
*/
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cctype>
#define up(a,b,c) for (int a(b),end##a(c);a<=end##a;++a)
#define down(a,c,b) for (int a(b),end##a(c);a>=end##a;--a)
#define uup(a,c,b) for (int a(b),end##a(c);a<=end##a;++a)
#define udown(a,b,c) for (int a(b),end##a(c);a>=end##a;--a)
#define endl '\n'
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
const double eps=1e-8;
const double PI=acos(-1.0);
typedef long long ll;
struct inout{
//吃掉io是我的习惯
};
inout io;
template<class T>void chkmin(T &a,T b){a=a<b?a:b;}
template<class T>void chkmax(T &a,T b){a=a>b?a:b;}
int beg[1024],to[102424],lst[102424],w[102424],s,t,k;
int fbeg[1024],fto[102424],flst[102424],fw[102424],e,inq[1024],dis[1024];
int q[10024240];
void spfa(int s){//在反图中跑最短路
int l,r;
l=r=1;
q[1]=s;
while(l<=r){
int u=q[l],v;
inq[u]=0;
for(int i=fbeg[u];i;i=flst[i]){
v=fto[i];
if(dis[v]>dis[u]+fw[i]){
dis[v]=dis[u]+fw[i];
if(!inq[v]){
inq[v]=1;
q[++r]=v;
}
}
}
++l;
}
}
typedef pair<int,pair<int,int> > pii;//形如(f(x),(g(x),x))
priority_queue<pii,vector<pii>,greater<pii> > pq;
#define x first
#define y second
#define mp make_pair
void add(int u,int v,int wea){//正边
to[++e]=v;
lst[e]=beg[u];
w[e]=wea;
beg[u]=e;
}
void fadd(int u,int v,int w){//反边
fto[e]=v;
flst[e]=fbeg[u];
fw[e]=w;
fbeg[u]=e;
}
void astar(int s){
pq.push(mp(dis[s],mp(0,s)));
pii u;
int sx,v;
if(dis[s]!=0x3f3f3f3f)
while(!pq.empty()){
u=pq.top();
sx=u.y.x;
pq.pop();
if(u.y.y==t){
--k;
if(!k){
io<<u.x<<endl;
return;
}
}
for(int i=beg[u.y.y];i;i=lst[i]){
v=to[i];
if(dis[v]!=0x3f3f3f3f)
pq.push(mp(sx+w[i]+dis[v],mp(sx+w[i],v)));//扩展
}
}
io<<-1<<endl;
}
int main(){
#ifdef cnyali_lk
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
io.init();
int n,m,u,v,w;
io>>n>>m;
up(i,1,m){
io>>u>>v>>w;
add(u,v,w);
fadd(v,u,w);
}
io>>s>>t>>k;
if(s==t)++k;//注意
up(i,1,n)dis[i]=0x3f3f3f3f;
dis[t]=0;
spfa(t);
astar(s);
io.out();
return 0;
}
文章目录
|

博客使用Disqus作为评论系统