[USACO Mar08] 奶牛跑步
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
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
Sample Output
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
动态规划， 图论， A*搜索， k短路
解析
今天考试竟然靠自己AC了这道题！！（所以不一定是正解）
首先，这题的意思很容易理解，
就是从n到1的路径中，求前k条最短的路径。
并且由于只能由高到低走，
所以拓扑排序都省了。
然后，我们维护一个优先队列q[i]表示能从1走到i点的所有路径:
priority_queue <int> q[];
然后，从终点1开始递推，
for(int i=;i<=n;i++)
每次枚举i所能到达的点j，再将每次前k短的路加上i,j的距离后加入到q[i]中
for(int j=head[i];j;j=e[j].to){
int l=e[j].next;
for(int t=;t<=k;t++){
if(q[l].empty()) break;
q[i].push(q[l].top()-e[j].w);
c[++c[]]=q[l].top();
q[l].pop();
}
for(int t=;t<=c[];t++){
q[l].push(c[t]);
}
c[]=;
}
最后，在从q[n]中输出前k短的路就行了（如果去q[n]为空就输出-1）。
for(int i=;i<=k;i++){
if(q[n].empty()){
puts("-1");
}
else{
printf("%d\n",-q[n].top());
q[n].pop();
}
}
时间复杂度为O(k*m)，应该能AC了！
上AC代码：
#include <bits/stdc++.h>
using namespace std; struct road{
int next,to,w;
}e[];
int n,m,k;
int head[],cnt=;
int c[];
priority_queue <int> q[]; void add(int x,int y,int w){
e[++cnt].to=head[x];
e[cnt].next=y;
e[cnt].w=w;
head[x]=cnt;
} int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=m;i++){
int x,y,w;
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
}
q[].push();
for(int i=;i<=n;i++){
for(int j=head[i];j;j=e[j].to){
int l=e[j].next;
for(int t=;t<=k;t++){
if(q[l].empty()) break;
q[i].push(q[l].top()-e[j].w);
c[++c[]]=q[l].top();
q[l].pop();
}
for(int t=;t<=c[];t++){
q[l].push(c[t]);
}
c[]=;
}
}
for(int i=;i<=k;i++){
if(q[n].empty()){
puts("-1");
}
else{
printf("%d\n",-q[n].top());
q[n].pop();
}
}
return ;
}