【USACO Mar08】奶牛跑步 A-star k短路

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条最短路经的长度.你的程序需要读入农场的地图, 一些从Xi到Yi的路径和它们的长度(Xi,Yi,Di).
所有(Xi,Yi,Di) 满足( 1<=Yi＜Xi; Yi＜Xi<=N, 1<=Di<=1,000,000 ).

Input

第1行: 3个数: N,M,K
第2..M+1行: 第 i+1行包含3个数 Xi,Yi,Di, 表示一条下坡的路.

Output

第1..K行: 第i行包含第i最短路径的长度,或−1如果这样的路径不存在.如果多条路径有同样的长度,请注意将这些长度逐一列出.

Sample Input

Sample Output

-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 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstring>
 5 #include <cstdio>
 6 #include <cmath>
 7 #include <queue>
 8 using namespace std;
 9 const int N=1005,M=10005;
10 int gi(){
11     int str=0;char ch=getchar();
12     while(ch>'9' || ch<'0')ch=getchar();
13     while(ch>='0' && ch<='9')str=(str<<1)+(str<<3)+ch-48,ch=getchar();
14     return str;
15 }
16 int n,m,k,head[N],num=0,Head[N],NUM=0;
17 struct Lin{
18     int next,to,dis;
19 }a[M<<1],b[M<<1];
20 void init2(int x,int y,int dis){
21     b[++NUM].next=Head[x];
22     b[NUM].to=y;
23     b[NUM].dis=dis;
24     Head[x]=NUM;
25 }
26 void init(int x,int y,int dis){
27     a[++num].next=head[x];
28     a[num].to=y;
29     a[num].dis=dis;
30     head[x]=num;
31 }
32 int f[N],qq[N*10],mod=N*10;bool vis[N];
33 void spfa()
34     {
35         int t=0,sum=1,x,u;
36         qq[1]=1;vis[1]=true;
37         memset(f,127/3,sizeof(f));
38         f[1]=0;
39         while(t!=sum)
40             {
41                 t++;t%=mod;
42                 x=qq[t];
43                 for(int i=Head[x];i;i=b[i].next){
44                         u=b[i].to;
45                         if(f[x]+a[i].dis<f[u]){
46                                 f[u]=f[x]+a[i].dis;
47                                 if(!vis[u])vis[u]=true,sum++,sum%=mod,qq[sum]=u;
48                          }
49                  }
50                 vis[x]=false;
51             }
52     }
53 struct node{
54     int x,dis,val;
55     bool operator<(const node &p)const{
56         return val>p.val;
57     }
58 };
59 priority_queue<node>q;
60 int cnt=1;
61 void Astar()
62     {
63         q.push((node){n,0,f[n]});
64         int u;node p;
65         while(!q.empty())
66             {
67                 p=q.top();q.pop();
68                 if(p.x==1)
69                     {
70                         if(cnt<=k)
71                             printf("%d
",p.dis),cnt++;
72                         if(cnt==k+1)return ;
73                     }
74                 for(int i=head[p.x];i;i=a[i].next)
75                     {
76                         u=a[i].to;
77                         q.push((node){u,p.dis+a[i].dis,p.dis+a[i].dis+f[u]});
78                     }
79             }
80     }
81 int main()
82 {
83     n=gi();m=gi();k=gi();
84     int x,y,z;
85     for(int i=1;i<=m;i++){
86         x=gi();y=gi();z=gi();
87         init(x,y,z);init2(y,x,z);
88     }
89     spfa();
90     Astar();
91     while(cnt<=k)printf("-1
"),cnt++;
92     return 0;
93 }