记录编号	315658	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2016-10-05 18:31:40	内存使用	0.77 MiB

/*
  Name: 牛跑步 
  Copyright: 
  Author: Go灬Fire 
  Date: 05/10/16 18:27
  Description: A*裸题，求k短路 
*/
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<queue>
#include<algorithm>
#define Begin freopen("cowjog.in","r",stdin);freopen("cowjog.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=15000;
struct Node{
	int num,dis,g,h;//g为实际已走距离，h为估计的距离 ，有向搜索 
	Node(){};
	Node(int a,int b){num=a;dis=b;}
	Node(int a,int b,int c){num=a;g=b;h=c;dis=g+h;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	} 
};
struct Edge{
	int next,to,dis;
}e[maxn];
int head[maxn],len,n,m,k,dis[maxn],from[maxn],to[maxn],date[maxn];
void Init();
void Insert(int x,int y,int z){
	len++;e[len].to=y;e[len].next=head[x];e[len].dis=z;head[x]=len;
}
void Dijs(int x){
	priority_queue<Node> q;
	memset(dis,0x7f,sizeof(dis));dis[x]=0;
	bool f[maxn]={0};f[x]=1;
	q.push(Node(x,dis[x]));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num;f[k]=1;
		for(int i=head[k];i;i=e[i].next){
			int j=e[i].to;
			if(!f[j] && dis[j]>dis[k]+e[i].dis){
				dis[j]=dis[k]+e[i].dis;
				q.push(Node(j,dis[j]));
			}
		}
	}
	//for(int i=1;i<=n;i++)printf("%d ",dis[i]);
}
void Astar(){
	memset(head,0,sizeof(head));memset(e,0,sizeof(e));len=0;
	for(int i=1;i<=m;i++)Insert(from[i],to[i],date[i]);//正向建边 
	priority_queue<Node> q;
	q.push(Node(n,0,dis[n]));
	while(!q.empty()){
		Node temp=q.top();q.pop();
		if(temp.num==1){
			printf("%d\n",temp.g);
			k--;
			if(k==0)return;
		}
		for(int i=head[temp.num];i;i=e[i].next){//从这个点进行扩展 
			q.push(Node(e[i].to,e[i].dis+temp.g,dis[e[i].to]));
		}
	}
	for(int i=1;i<=k;i++)printf("-1\n");
}
int main(){
    Begin;
    Init();
    //system("pause");
    End;
    return 0;
}
void Init(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&from[i],&to[i],&date[i]);
		Insert(to[i],from[i],date[i]);//建立反向边，以求dis数组 
	}
	Dijs(1);//以终点为起点，求出估价函数dis数组，进行启发式搜索 
	Astar();//A星 
}
//0 1 1 5 1 1