牛跑步

Time Limit: 10 Sec Memory Limit: 162 MB

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

Sample Output

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

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
102
103
104
105
106
107
108
109
#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+5;

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=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    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[10000001];
    memset(dist,63,sizeof(dist));
    tou = 0; wei = 1;
    vis[x] = 1; dist[x] = 0; q[1] = 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] = 1, q[++wei] = v;
            }
        }
        vis[u] = 0;
    }
}

void Astar()
{
    priority_queue <power> q;
    q.push( (power){S, 0, 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=1;
    for(int i=1;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,0,sizeof(first));  tot=0;
    for(int i=1;i<=m;i++) Add(a[i].x,a[i].y,a[i].z);

    Astar();

    for(int i=1;i<=k;i++)
        printf("%d\n",Ans[i]!=0?Ans[i]:-1);

}