记录编号	160234	评测结果	AAAAAAAAAA
题目名称	KZ菌的星际旅行	最终得分	100
用户昵称	KZNS	是否通过	通过
代码语言	C++	运行时间	0.148 s
提交时间	2015-04-24 19:29:19	内存使用	16.52 MiB

#include<queue>
#include<vector>
#include<fstream>
using namespace std;
ifstream cin("KZstartravelillu.in");
ofstream cout("KZstartravelillu.out");
const int ma=1000000;
class poi{
public:
	int p,q;
};
vector<poi>mp[ma];
bool uing[ma]={false};
int end[ma];
int main(){
	int n,m;
	cin>>n>>m;
	int a,b,s;
	poi us;
	for(int i=0;i<m;i++){
		cin>>a>>b>>s;
		us.q=s;
		us.p=b;
		mp[a].push_back(us);
		us.p=a;
		mp[b].push_back(us);
	}
	queue<int>ls;
	for(int i=0;i<ma;i++)
		end[i]=2147483646;
	end[1]=0;
	ls.push(1);
	uing[1]=true;
	while(!ls.empty()){
		int u=ls.front();
		ls.pop();
		uing[u]=false;
		for(int i=0;i<mp[u].size();i++){
			if(end[u]+mp[u][i].q<end[mp[u][i].p]){
				end[mp[u][i].p]=end[u]+mp[u][i].q;
				if(!uing[mp[u][i].p]){
					ls.push(mp[u][i].p);
					uing[mp[u][i].p]=true;
				}
			}
		}
	}
	cout<<end[n]*2<<endl;
	return 0;
}