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

* 第1行: 3个数: N, M, 和K

* 第 2..M+1行: 第 i+1 行包含3个数 X_i, Y_i, 和 D_i, 表示一条下坡的路.

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

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

1
2
2
3
6
7
-1

输出解释:

路经分别为(5-1), (5-3-1), (5-2-1), (5-3-2-1), (5-4-3-1),

(5-4-3-2-1).

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define N 100010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

int lj[N],fro[N],to[N],v[N],cnt;

inline void add(int a,int b,int c){fro[++cnt]=lj[a];to[cnt]=b;v[cnt]=c;lj[a]=cnt;}

int lj2[N],fro2[N],to2[N],v2[N],cnt2;

inline void add2(int a,int b,int c){fro2[++cnt2]=lj2[a];to2[cnt2]=b;v2[cnt2]=c;lj2[a]=cnt2;}

int q[N*],ji[N];

ll dis[N];

int n,m,k;

bool vs[N];

void spfa()

{

    memset(dis,0x3f,sizeof(dis));

    int l=,r=,x;

    dis[]=;vs[]=;

    q[]=;

    while(l<r)

    {

        x=q[l++];vs[x]=;

        for(int i=lj2[x];i;i=fro2[i])

        {

            if(dis[to2[i]]>dis[x]+v2[i])

            {

                dis[to2[i]]=dis[x]+v2[i];

                if(!vs[to2[i]]){vs[to2[i]]=;q[r++]=to2[i];}

            }

        }

    }

}

struct qaz

{

    int x;ll h,g;

    bool operator <(const qaz &a)const

    {return g+h>a.g+a.h;}

};

ll ans[N],tot;

void Astar()

{

    priority_queue<qaz>q;

    q.push((qaz){n,,dis[n]});

    qaz tp;int x;

    while(!q.empty())

    {

        tp=q.top();q.pop();

        x=tp.x;vs[x]=;

        ji[x]++;

        if(ji[x]>k) continue;

        if(x==) ans[++tot]=tp.g+tp.h;

        if(tot==k) return;

        for(int i=lj[x];i;i=fro[i])

            q.push((qaz){to[i],tp.h+v[i],dis[to[i]]});

    }

}

int main()

{

    n=rd();m=rd();k=rd();

    int x,y,d;

    for(int i=;i<=m;i++)

    {

        x=rd();y=rd();d=rd();

        if(x<y) swap(x,y);

        add(x,y,d);add2(y,x,d);

    }

    spfa();

    memset(ans,-,sizeof(ans));

    Astar();

    for(int i=;i<=k;i++) printf("%lld\n",ans[i]);

    return ;

}