记录编号	328450	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.135 s
提交时间	2016-10-24 07:33:03	内存使用	0.55 MiB

#include<cmath>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cstdio>
#include<queue> 
using namespace std;
const int maxn=1010;
struct Node{
	int num,dis;
	Node(){};
	Node(int a,int b){num=a;dis=b;}
	bool operator < (const Node & a)const{
		return dis>a.dis;
	}
} ;
struct Edge{
	int next,to,dis;
}e[10005*2];
int n,m,head[maxn],len;
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 Init();
void Dijs(int x){
	int dis[maxn];memset(dis,0x7f,sizeof(dis));dis[x]=0;
	bool f[maxn]={0};f[x]=1;
	priority_queue<Node> q;
	q.push(Node(x,dis[x])); 
	while(!q.empty()){
		Node temp=q.top();q.pop();
		int k=temp.num;f[k]=1;
		if(k==n){printf("%d\n",temp.dis);return;}
		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]));
			}
		} 
	}
	printf("-1\n");
}
int main(){
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout); 
	int T;scanf("%d",&T);
	while(T--)Init();
    getchar();getchar();
    return 0;
}
void Init(){
	memset(e,0,sizeof(e));memset(head,0,sizeof(head));len=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z;scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);Insert(y,x,z);
	} 
	Dijs(1);
}