首页 > 代码库 > 【BZOJ1598】牛跑步 [A*搜索]
【BZOJ1598】牛跑步 [A*搜索]
牛跑步
Time Limit: 10 Sec Memory Limit: 162 MB[Submit][Status][Discuss]
Description
BESSIE准备用从牛棚跑到池塘的方法来锻炼.
但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚.
BESSIE也不想跑得太远,所以她想走最短的路经.
农场上一共有M 条路, 每条路连接两个用1..N标号的地点.
更方便的是,如果X>Y,则地点X的高度大于地点Y的高度.
地点N是BESSIE的牛棚;地点1是池塘.
很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经.
请帮助BESSIE找出这K条最短路经的长度.
你的程序需要读入农场的地图,一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i).
Input
第1行: 3个数: N, M, 和K
第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.
Output
第1..K行: 第i行包含第i最短路经的长度,或-1如果这样的路经不存在.如果多条路经有同样的长度,请注意将这些长度逐一列出.
Sample Input
5 8 7
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1
5 4 1
5 3 1
5 2 1
5 1 1
4 3 4
3 1 1
3 2 1
2 1 1
Sample Output
1
2
2
3
6
7
-1
2
2
3
6
7
-1
HINT
1 <= M <= 10,000, 1 <= N <= 1000, 1 <= K <= 100
Main idea
给定一张图，输出1~k短路的距离。
Solution
既然是求k短路，那我们使用A*搜索，先反向建图，记录终点到每一个点的最短路，然后把这个dist当做估价来跑A*即可。可以证明：第k次搜到的路即是k短路。
Code
1 #include<iostream> 2 #include<string> 3 #include<algorithm> 4 #include<cstdio> 5 #include<cstring> 6 #include<cstdlib> 7 #include<cmath> 8 #include<queue> 9 using namespace std; 10 typedef long long s64; 11 12 const int ONE = 2e6+5; 13 14 int n,m,k; 15 int S,T; 16 int dist[ONE],vis[ONE],Output[ONE],tou,wei; 17 int next[ONE],first[ONE],go[ONE],w[ONE],tot; 18 int Ans[ONE],num; 19 20 struct point 21 { 22 int x,y,z; 23 }a[ONE]; 24 25 struct power 26 { 27 int x,real,eva; 28 bool operator <(const power &a) const 29 { 30 return a.real + a.eva < real + eva; 31 } 32 }; 33 34 inline int get() 35 { 36 int res=1,Q=1; char c; 37 while( (c=getchar())<48 || c>57) 38 if(c==‘-‘)Q=-1; 39 if(Q) res=c-48; 40 while((c=getchar())>=48 && c<=57) 41 res=res*10+c-48; 42 return res*Q; 43 } 44 45 void Add(int u,int v,int z) 46 { 47 next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z; 48 } 49 50 void SPFA(int x) 51 { 52 int q[10000001]; 53 memset(dist,63,sizeof(dist)); 54 tou = 0; wei = 1; 55 vis[x] = 1; dist[x] = 0; q[1] = x; 56 while(tou < wei) 57 { 58 int u = q[++tou]; 59 for(int e=first[u];e;e=next[e]) 60 { 61 int v = go[e]; 62 if(dist[v] > dist[u] + w[e]) 63 { 64 dist[v] = dist[u] + w[e]; 65 if(!vis[v]) vis[v] = 1, q[++wei] = v; 66 } 67 } 68 vis[u] = 0; 69 } 70 } 71 72 void Astar() 73 { 74 priority_queue <power> q; 75 q.push( (power){S, 0, dist[S]} ); 76 while(!q.empty()) 77 { 78 power u = q.top(); q.pop(); 79 if(u.x == T) Ans[++num] = u.real; 80 if(++Output[u.x] > k) continue; 81 if(Output[T] == k) return; 82 for(int e=first[u.x]; e; e=next[e]) 83 { 84 int v=go[e]; 85 q.push( (power){v, u.real+w[e], dist[v]} ); 86 } 87 } 88 } 89 90 int main() 91 { 92 n=get(); m=get(); k=get(); 93 S=n, T=1; 94 for(int i=1;i<=m;i++) 95 { 96 a[i].x=get(); a[i].y=get(); a[i].z=get(); 97 Add(a[i].y, a[i].x, a[i].z); 98 } 99 SPFA(T);100 101 memset(first,0,sizeof(first)); tot=0;102 for(int i=1;i<=m;i++) Add(a[i].x,a[i].y,a[i].z);103 104 Astar();105 106 for(int i=1;i<=k;i++)107 printf("%d\n",Ans[i]!=0?Ans[i]:-1);108 109 }
【BZOJ1598】牛跑步 [A*搜索]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。