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

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
vector<int> g[1000001],c[1000001];
int f[1000001]={0};
bool l[1000001]={0};
int n,m;
ifstream in("KZstartravelillu.in");
ofstream out("KZstartravelillu.out");
void SPFA(int s)
{
	int i;
	queue<int> q;
	for(i=1;i<=100001;i++)
	{
		l[i]=0;
		f[i]=999999999;
	}
	l[s]=1;
	f[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		l[u]=0;
		for(i=0;i<g[u].size();i++)
		{
			int v=g[u][i];
			if(f[v]>f[u]+c[u][i])
			{
				f[v]=f[u]+c[u][i];
				if(!l[v])
				{
					l[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	int i,a,b,d;
	in>>n>>m;
	for(i=1;i<=m;i++)
	{
		in>>a>>b>>d;
		g[a].push_back(b);
		g[b].push_back(a);
		c[a].push_back(d);
		c[b].push_back(d);
	}
	SPFA(1);
	for(i=n;i<=n;i++)out<<f[i]*2<<endl;
	return 0;
}