「BZOJ1598」[Usaco2008 Mar] 牛跑步
Description
BESSIE准备用从牛棚跑到池塘的方法来锻炼. 但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚. BESSIE也不想跑得太远,所以她想走最短的路经. 农场上一共有M (1 <= M <= 10,000)条路, 每条路连接两个用1..N(1 <= N <= 1000)标号的地点. 更方便的是,如果X>Y,则地点X的高度大于地点Y的高度. 地点N是BESSIE的牛棚;地点1是池塘. 很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K (1 <= K <= 100)条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经. 请帮助BESSIE找出这K条最短路经的长度.你的程序需要读入农场的地图, 一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i). 所有(X_i, Y_i, D_i)满足(1 <= Y_i < X_i; Y_i < X_i <= N, 1 <= D_i <= 1,000,000).
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 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
2
2
3
6
7
-1
HINT
输出解释:
路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),
(5-4-3-2-1)。
题解
K短路裸题
1 A*算法
h(n)=f(n)+g(n)
其中f(n)是节点n的估价函数，g(n)表示实际状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。另外定义h'(n)为n到目标节点最佳路径的实际值。如果h'(n)≥h(n)则如果存在从初始状态走到目标状态的最小代价的解，那么用该估价函数搜索的算法就叫A*算法。
2
|
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 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<cmath> #include<algorithm> #include<map> #include<ext/pb_ds/priority_queue.hpp> #define pa pair<int,int> #define inf 2000000000 using namespace std; using namespace __gnu_pbds; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } typedef __gnu_pbds::priority_queue<pa,greater<pa> > heap; int n,m,K,cnt,cnt2; int ans[105]; int d[10005],g[10005],tim[10005]; int last[10005],last2[10005]; heap q; heap::point_iterator id[10005]; struct edge{int to,next,v;}e[10005],ed[10005]; void insert(int u,int v,int w) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w; ed[++cnt2].to=u;ed[cnt].next=last2[v];last2[v]=cnt2;ed[cnt2].v=w; } void dijkstra() { for(int i=1;i<=n;i++)d[i]=inf; d[1]=0; id[1]=q.push(make_pair(0,1)); while(!q.empty()) { int now=q.top().second;q.pop(); for(int i=last2[now];i;i=ed[i].next) if(ed[i].v+d[now]<d[ed[i].to]) { d[ed[i].to]=d[now]+ed[i].v; if(id[ed[i].to]!=0) q.modify(id[ed[i].to],make_pair(d[ed[i].to],ed[i].to)); else id[ed[i].to]=q.push(make_pair(d[ed[i].to],ed[i].to)); } } } void astar() { if(d[n]==inf)return; q.push(make_pair(d[n],n)); while(!q.empty()) { int now=q.top().second,dis=q.top().first;q.pop(); tim[now]++; if(now==1)ans[tim[now]]=dis; if(tim[now]<=K) for(int i=last[now];i;i=e[i].next) q.push(make_pair(dis-d[now]+d[e[i].to]+e[i].v,e[i].to)); } } int main() { n=read();m=read();K=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(),w=read(); insert(u,v,w); } dijkstra(); astar(); for(int i=1;i<=K;i++) if(ans[i])printf("%d\n",ans[i]); else puts("-1"); return 0; } |
OI 课件=>
