记录编号	248162	评测结果	AAAAAAAAAA
题目名称	[USACO Mar08] 牛跑步	最终得分	100
用户昵称	哒哒哒哒哒！	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2016-04-10 08:34:00	内存使用	3.36 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<cstring>

using namespace std;

const int maxnode=100000;
const int maxedge=100000;
struct Edge{
	int to,dis,next;
}e[maxedge];
struct Node{
	int dist,num;
	int g,h;
	Node(int x,int y){
		num=x;dist=y;
	}
	Node(int x,int y,int z){
		num=x;g=y;h=z;
		dist=g+h;
	}
	bool operator <(const Node &x)const{
		return dist>x.dist;
	}
};
int tot,head[maxnode],dis[maxnode];
int nodecount,edgecount,k;
int from[maxnode],to[maxnode],val[maxnode];
void edge(int u,int v,int w)
{
	e[++tot].to=v;
	e[tot].dis=w;
	e[tot].next=head[u];
	head[u]=tot;
}

void dijkstra(int s)
{
	memset(dis,127/3,sizeof(dis));
	priority_queue<Node>que;
	dis[s]=0;
	que.push(Node(s,0));
	while(!que.empty()){
		Node node=que.top();que.pop();
		s=node.num;
		if(dis[s]!=node.dist) continue;
		for(int i=head[s];i;i=e[i].next){
			int to=e[i].to;
			if(dis[to]>dis[s]+e[i].dis){
				dis[to]=dis[s]+e[i].dis;
				que.push(Node(to,dis[to]));
			}
		}
	}
}

void clear()
{
	memset(e,0,sizeof(e));
	memset(head,0,sizeof(head));
	tot=0;
}
void secondedge()
{
	for(int i=1;i<=edgecount;i++)
		edge(from[i],to[i],val[i]);
}

void Astar(int s,int t,int k)
{
	dijkstra(t);
	priority_queue<Node>q;
	clear();
	secondedge();
	q.push(Node(s,0,dis[s]));
	while(!q.empty()){
		Node x=q.top();q.pop();
		if(x.num==t){
			printf("%d\n",x.g);
			k--;
			if(k==0) return ;
		}
		for(int i=head[x.num];i;i=e[i].next){
			q.push(Node(e[i].to,x.g+e[i].dis,dis[e[i].to]));
		}
	}
	for(int i=1;i<=k;i++) printf("-1\n");
	return;
}

int main()
{
	freopen("cowjog.in","r",stdin);
    freopen("cowjog.out","w",stdout);
	scanf("%d%d%d",&nodecount,&edgecount,&k);
	for(int i=1;i<=edgecount;i++){
		scanf("%d%d%d",&from[i],&to[i],&val[i]);
		edge(to[i],from[i],val[i]);
	}
	Astar(nodecount,1,k);
	return 0;
}