记录编号	247932	评测结果	AAAAAAAAAA
题目名称	133.[USACO Mar08] 牛跑步	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2016-04-09 20:53:38	内存使用	0.00 MiB

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
namespace cat{
	const int maxn = 10000 + 10 ;
	void read(int &x){
		x=0;char ch;
		while(ch=getchar(),ch<'!');
		while(x=10*x+ch-'0',ch=getchar(),ch>'!');
	}
	struct Edge{
		int next,to,dis;
	}G[maxn<<1];
	int head[maxn],from[maxn],to[maxn],dis[maxn];
	int val[maxn];
	int cnt = 1,n,m,K;
	void add(int u,int v,int dis){
		G[++cnt].to = v;
		G[cnt].dis = dis;
		G[cnt].next = head[u];
		head[u] = cnt;
	}
	struct Node{
		int num,dist,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;
		}
	};
	void dijkstra(int s){
		priority_queue<Node>Q;
		memset(dis,127/3,sizeof(dis));
		dis[s] = 0;
		Q.push( Node(s,0) );
		while(!Q.empty()){
			Node t = Q.top();Q.pop();
			int x = t.num ;
			if( t.dist != dis[t.num] ) continue;
			for(int i=head[x];i;i=G[i].next){
				if( dis[G[i].to] > dis[x] + G[i].dis ){
					dis[G[i].to] = dis[x] + G[i].dis;
					Q.push( Node(G[i].to,dis[G[i].to]) );
				}
			}
		}
	}
	void A_star(int s,int t,int k){
		priority_queue<Node>Q;
		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 ) return;
			}
			for(int i=head[x.num];i;i=G[i].next){
				Q.push(Node(G[i].to,x.g+G[i].dis,dis[G[i].to]));
			}
		}
		for(int i=1;i<=k;i++) printf("-1\n");
		return;
	}
	int doo(){
		freopen("cowjog.in","r",stdin);
		freopen("cowjog.out","w",stdout);
		//freopen("in.txt","r",stdin);
		int k;
		read(n);read(m);read(k);
		for(int i=1;i<=m;i++){
			read(from[i]);read(to[i]);read(val[i]);
			add(to[i],from[i],val[i]);
		}
		int s = n,t = 1;
		dijkstra(t);
	//	for(int i=1;i<=n;i++) printf("%d ",dis[i]);
	//	printf("\n");
		memset(G,0,sizeof(G));
		memset(head,0,sizeof(head));
		cnt = 1;
		for(int i=1;i<=m;i++){
			add(from[i],to[i],val[i]);
		//	printf("%d -> %d = %d\n",from[i],to[i],val[i]);
		}
		A_star(s,t,k);
	}
}
int ans = cat::doo();
int main(){;}