题解 [USACO Mar08] 奶牛跑步

[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 ;
}
上一篇:CentOS7.x关闭防火墙


下一篇:MySQL错误:You are using safe update mode and you tried to update a table without a WHERE that uses a K