牛跑步
Time Limit: 10 Sec Memory Limit: 162 MB
[Submit][Status][Discuss]
Description
BESSIE准备用从牛棚跑到池塘的方法来锻炼.
但是因为她懒,她只准备沿着下坡的路跑到池塘, 然后走回牛棚.
BESSIE也不想跑得太远,所以她想走最短的路经.
农场上一共有M 条路, 每条路连接两个用1..N标号的地点.
更方便的是,如果X>Y,则地点X的高度大于地点Y的高度.
地点N是BESSIE的牛棚;地点1是池塘.
很快, BESSIE厌倦了一直走同一条路.所以她想走不同的路,更明确地讲,她想找出K条不同的路经.为了避免过度劳累,她想使这K条路经为最短的K条路经.
请帮助BESSIE找出这K条最短路经的长度.
你的程序需要读入农场的地图,一些从X_i到Y_i 的路经和它们的长度(X_i, Y_i, D_i).
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
1 <= M <= 10,000, 1 <= N <= 1000, 1 <= K <= 100
Main idea
给定一张图，输出1~k短路的距离。
Solution
既然是求k短路，那我们使用A*搜索，先反向建图，记录终点到每一个点的最短路，然后把这个dist当做估价来跑A*即可。可以证明：第k次搜到的路即是k短路。
Code
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<queue>
using namespace std;
typedef long long s64; const int ONE = 2e6+; int n,m,k;
int S,T;
int dist[ONE],vis[ONE],Output[ONE],tou,wei;
int next[ONE],first[ONE],go[ONE],w[ONE],tot;
int Ans[ONE],num; struct point
{
int x,y,z;
}a[ONE]; struct power
{
int x,real,eva;
bool operator <(const power &a) const
{
return a.real + a.eva < real + eva;
}
}; inline int get()
{
int res=,Q=; char c;
while( (c=getchar())< || c>)
if(c=='-')Q=-;
if(Q) res=c-;
while((c=getchar())>= && c<=)
res=res*+c-;
return res*Q;
} void Add(int u,int v,int z)
{
next[++tot]=first[u]; first[u]=tot; go[tot]=v; w[tot]=z;
} void SPFA(int x)
{
int q[];
memset(dist,,sizeof(dist));
tou = ; wei = ;
vis[x] = ; dist[x] = ; q[] = x;
while(tou < wei)
{
int u = q[++tou];
for(int e=first[u];e;e=next[e])
{
int v = go[e];
if(dist[v] > dist[u] + w[e])
{
dist[v] = dist[u] + w[e];
if(!vis[v]) vis[v] = , q[++wei] = v;
}
}
vis[u] = ;
}
} void Astar()
{
priority_queue <power> q;
q.push( (power){S, , dist[S]} );
while(!q.empty())
{
power u = q.top(); q.pop();
if(u.x == T) Ans[++num] = u.real;
if(++Output[u.x] > k) continue;
if(Output[T] == k) return;
for(int e=first[u.x]; e; e=next[e])
{
int v=go[e];
q.push( (power){v, u.real+w[e], dist[v]} );
}
}
} int main()
{
n=get(); m=get(); k=get();
S=n, T=;
for(int i=;i<=m;i++)
{
a[i].x=get(); a[i].y=get(); a[i].z=get();
Add(a[i].y, a[i].x, a[i].z);
}
SPFA(T); memset(first,,sizeof(first)); tot=;
for(int i=;i<=m;i++) Add(a[i].x,a[i].y,a[i].z); Astar(); for(int i=;i<=k;i++)
printf("%d\n",Ans[i]!=?Ans[i]:-); }