记录编号	160231	评测结果	AAAAWAWWWW
题目名称	KZ菌的星际旅行	最终得分	50
用户昵称	fyb	是否通过	未通过
代码语言	C++	运行时间	1.593 s
提交时间	2015-04-24 19:22:19	内存使用	191.04 MiB

#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

#define NMAX 10000000
#define VERY_LARGE 200000000000ll

struct node{
	int ind;
	long long d;

	bool operator < (const node b)const{d>b.d;}
};

struct edge{
	int u,v,w;
};

long long d[NMAX+1];
vector<edge> g[NMAX+1];
priority_queue<node> q;

int main(){
	int n,m;
	node tn;
	edge te;
	int tmp;
	int ans;
	int i;

	freopen("KZstartravelillu.in","r",stdin);
	freopen("KZstartravelillu.out","w",stdout);

	scanf("%d%d",&n,&m);
	getchar();
	for(i=0;i<m;i++){
		scanf("%d%d%d",&te.u,&te.v,&te.w);
//		getchar();
		g[te.u].push_back(te);
		tmp=te.u;
		te.u=te.v;
		te.v=tmp;
		g[te.u].push_back(te);
	}

	for(i=2;i<=n;i++)d[i]=VERY_LARGE;
	d[1]=0;
	q.push((node){1,0});

	while(!q.empty()){
		tn=q.top();
		q.pop();
		if(tn.d!=d[tn.ind])continue;
		for(i=0;i<g[tn.ind].size();i++){
			edge & e=g[tn.ind][i];
			if(d[tn.ind]+e.w<d[e.v]){
				d[e.v]=d[tn.ind]+e.w;
				q.push((node){e.v,d[e.v]});
			}
		}
	}

	ans=d[n]*2;
	printf("%d\n",ans);
	return 0;
}