记录编号	221677	评测结果	AAAAA
题目名称	最难的任务	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.086 s
提交时间	2016-01-25 14:30:03	内存使用	0.54 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 205,maxm = 20010; 
struct edge{
	int to,next,w;
}lst[maxm];
int n,m,len,first[maxn];
void insert(int v1,int v2,int cost){
	lst[len].to = v2;
	lst[len].next = first[v1];
	lst[len].w = cost;
	first[v1] = len++;
}
struct node{
	int to,w;
	bool operator < (const node& a)const{
		return w>a.w;
	}
	node(int _to,int _w){
		to = _to;w = _w;
	}
};
bool vis[maxn];
int dis[maxn];
void dij(){
	priority_queue<node> q;
	q.push(node(1,0));
	while(!q.empty()){
		while(!q.empty()&&vis[q.top().to])q.pop();
		if(q.empty())break;
		dis[q.top().to] = q.top().w;
		int j = q.top().to;
		vis[j] = true;
		q.pop();
		for(int pt = first[j];pt;pt = lst[pt].next){
			if(!vis[lst[pt].to])q.push(node(lst[pt].to,dis[j]+lst[pt].w));
		}
	}
}
int main(){
	freopen("hardest.in","r",stdin);
	freopen("hardest.out","w",stdout);
	int t;
	scanf("%d",&t);
	for(;t;--t){
		scanf("%d %d",&n,&m);
		if(n==1){
			printf("0\n");
			continue;
		}
		memset(dis,0,sizeof(dis));
		memset(vis,0,sizeof(vis));
		memset(first,0,sizeof(first));
		len = 1;
		int a,b,c;
		for(int i = 0;i<m;++i){
			scanf("%d %d %d",&a,&b,&c);
			insert(a,b,c);
			insert(b,a,c);
		}
		dij();
		if(dis[n])printf("%d\n",dis[n]);
		else printf("-1\n");
	}
	fclose(stdin);fclose(stdout);	
}