记录编号	271180	评测结果	ATWTTTTWET
题目名称	[USACO Mar08] 牛跑步	最终得分	10
用户昵称	Sky_miner	是否通过	未通过
代码语言	C++	运行时间	6.918 s
提交时间	2016-06-15 18:32:40	内存使用	2.19 MiB

#include<iostream>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>
#include<time.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<iomanip>
#include<functional>
#define JW fclose(stdin); fclose(stdout);
#define WJ(name) freopen(#name".in","r",stdin); freopen(#name".out","w",stdout);
using namespace std;
const long long maxn=1010;
long long dis[maxn<<2],zhead[maxn*30],zlen=0,fhead[maxn*30],flen=0,n,flag,m;
inline long long QR(){
	char ch;
	while(ch=getchar(),ch<'0'||ch>'9');
	long long x=ch-48;
	while(ch=getchar(),ch>='0'&&ch<='9')x=x*10+ch-48;
	return x;
}
struct EDGE{
	long long to,next,w;
};
EDGE zedge[maxn*30],fedge[maxn*30];
inline void faddedge(long long from,long long to,long long w){
	++flen;
	fedge[flen].to=to;
	fedge[flen].w=w;
	fedge[flen].next=fhead[from];
	fhead[from]=flen;
}
inline void zaddedge(long long from,long long to,long long w){
	++zlen;
	zedge[zlen].to=to;
	zedge[zlen].w=w;
	zedge[zlen].next=zhead[from];
	zhead[from]=zlen;
}
struct DJS{
	long long id,juli;
	DJS(long long x=0,long long y=0){
		id=x,juli=y;
	}
	bool operator < (const DJS& a)const {
		return juli>a.juli;
	}
};
void Djs(long long s){
	#define k fedge[i].to
	#define w fedge[i].w
	memset(dis,0x7f,sizeof(dis));
	dis[s]=0;
	priority_queue<DJS>q;DJS a;
	q.push(DJS(s,0));
	while(!q.empty()){
		a=q.top();
		q.pop();
		if(a.juli!=dis[a.id])continue;
		for(long long i=fhead[a.id];i!=-1;i=fedge[i].next)
			if(dis[k]>dis[a.id]+w){
				dis[k]=dis[a.id]+w;
				q.push(DJS(k,dis[k]));
			}
	}
	#undef k
	#undef w
}
struct node{
	long long h,id;
	node(long long x=0,long long y=0){
		id=x,h=y;
	}
	bool operator < (const node& a)const {
		return h+dis[id]>a.h+dis[a.id];
	}
};
void astar(){
	priority_queue<node>que;
	node x;
	que.push(node(n,0));
	while(!que.empty()){
		x=que.top();
		que.pop();
		if(x.id==1){
			printf("%d\n",x.h);
			flag--;
			continue;
		}
		for(long long i=zhead[x.id];i!=-1;i=zedge[i].next)que.push(node(zedge[i].to,x.h+zedge[i].w));
	}
	for(long long i=1;i<=flag;i++)printf("-1\n");
}
int main(){
	freopen("cowjog.in","r",stdin);
	freopen("cowjog.out","w",stdout);
	n=QR(),m=QR(),flag=QR();
	long long a,b,c;
	memset(zhead,-1,sizeof(zhead));
	memset(zedge,-1,sizeof(zedge));
	memset(fhead,-1,sizeof(fhead));
	memset(fedge,-1,sizeof(fedge));
	for(long long i=1;i<=m;i++){
		a=QR(),b=QR(),c=QR();
		if(a<b)swap(a,b);
		faddedge(b,a,c);
		zaddedge(a,b,c);
	}
	Djs(1);
	astar();
	return 0;
}