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 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
输出解释:
路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),
(5-4-3-2-1).
Source
Gold
Solution
裸的求第k短路。
|
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 |
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; const int N=1005,M=10005; int n,m,k,tot,tot1,num,Next[M],head[N],tree[M],val[M]; int Next1[M],head1[N],tree1[M],val1[M],dis[N],x[N<<1]; bool visit[N]; struct node{int u,dis;}; struct cmp { bool operator()(node a,node b) { return a.dis+dis[a.u]>b.dis+dis[b.u]; } }; priority_queue<node,vector<node>,cmp> Q; void add(int x,int y,int z) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; val[tot]=z; } void Add(int x,int y,int z) { tot1++; Next1[tot1]=head1[x]; head1[x]=tot1; tree1[tot1]=y; val1[tot1]=z; } void spfa() { int t=0,w=1; for (int i=1;i<=n;i++) visit[i]=false,dis[i]=1<<29; x[1]=1;visit[1]=true;dis[1]=0; while (t!=w) { int u=x[++t]; if (t>n*2) t=1; visit[u]=false; for (int i=head1[u];i;i=Next1[i]) { int v=tree1[i]; if (dis[v]>dis[u]+val1[i]) { dis[v]=dis[u]+val1[i]; if (!visit[v]) { x[++w]=v; if (w>n*2) w=1; visit[v]=true; } } } } } void A_star() { node t; t.u=n;t.dis=0; Q.push(t); while (!Q.empty()) { t=Q.top(); Q.pop(); int u=t.u,Dis=t.dis; if (u==1) { num++; printf("%d\n",Dis); if (num>=k) return; continue; } for (int i=head[u];i;i=Next[i]) { int v=tree[i]; t.u=v;t.dis=Dis+val[i]; Q.push(t); } } } int main() { scanf("%d%d%d",&n,&m,&k); tot=tot1=num=0; for (int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z);Add(y,x,z); } spfa(); A_star(); for (int i=num+1;i<=k;i++) puts("-1"); return 0; } |
