记录编号	131833	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	高哥	是否通过	通过
代码语言	C++	运行时间	0.072 s
提交时间	2014-10-24 21:48:29	内存使用	0.55 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#define MAX 1<<29
#define N 500
#define M 10010
using namespace std;
int head[N],nex[2*M],to[2*M],c[2*M];
int tot=0,d[N],res;
struct node{
	int i,d;
	bool operator < (const node& rhs) const{
		return d>rhs.d;
	}
};
void add(int u,int v,int w)
{
	nex[++tot]=head[u];
	head[u]=tot;
	to[tot]=v;
	c[tot]=w;
}
priority_queue<node> que;
int djs()
{
	 d[res]=0;
	 que.push((node){res,0});
	 while(!que.empty())
	 {
	 	node u=que.top();
	 	que.pop();
	 	for(int i=head[u.i];i!=-1;i=nex[i])
	 	{
	 		int v=to[i];
	 		if(d[v]>d[u.i]+c[i])
	 		{
	 			d[v]=d[u.i]+c[i];
	 			que.push((node){v,d[v]});
	 		}
	 	}
	 }
}
int main()
{
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	int n,m;
	int t,cas=0;
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		memset(head,-1,sizeof(head));
		memset(to,0,sizeof(to));
		memset(c,0,sizeof(c));
		memset(nex,0,sizeof(nex));
		tot=0;
		for(int i=0;i<=n;i++)
			d[i]=MAX;
		for(int i=1;i<=m;i++)
		{
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,w);
		}
		res=1;
		djs();
		
		printf("%d\n",(d[n]==MAX? -1 : d[n]));
	}
	return 0;
}