记录编号	47198	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]逃离遗迹	最终得分	100
用户昵称	Cloud	是否通过	通过
代码语言	C++	运行时间	0.344 s
提交时间	2012-10-31 10:19:47	内存使用	3.50 MiB

#include<fstream>
#include<queue>
#include<set>
using namespace std;
struct yu
{
	int u,v,w;
};
struct cmp
{
	int operator()(const yu &e1,const yu &e2)
	{
		if(e1.u<e2.u)
			return 1;
		else
			return 0;
	}
};
yu tmp;
multiset<yu,cmp> s;
multiset<yu,cmp>::iterator p;
struct qu
{
	int q,sum;
};
queue<qu> dq;
qu t;
int f[20001][3];
int main(void)
{
	ifstream fin("escapeb.in");
	ofstream fout("escapeb.out");
	
	int n,a[3];
	fin>>n>>a[0]>>a[1]>>a[2];
	int i,j,k;
	for(i=0;i<n;i++)
	{
		fin>>tmp.u>>tmp.v>>tmp.w;
		s.insert(tmp);
		k=tmp.u;
		tmp.u=tmp.v;
		tmp.v=k;
		s.insert(tmp);
	}
	for(i=0;i<3;i++)
	{
		t.q=a[i];
		t.sum=0;
		dq.push(t);
		while(dq.size())
		{
			t=dq.front();
			tmp.u=t.q;
			p=s.upper_bound(tmp);
			p--;
			j=t.q,k=t.sum;
			for(;p->u==j;p--)
			{
				if(!f[p->v][i])
				{
					f[p->v][i]=k+p->w;
					t.sum=k+p->w;
					t.q=p->v;
					dq.push(t);
				}
			}
			dq.pop();
		}
	}
	f[a[0]][0]=0;
	f[a[1]][1]=0;
	f[a[2]][2]=0;
	int min=~0u>>1;
	for(i=1;i<=n;i++)
		if(f[i][0]+f[i][1]+f[i][2]<min)
		{
			j=i;
			min=f[i][0]+f[i][1]+f[i][2];
		}
	fout<<j<<endl<<min;	
	fin.close();
	fout.close();
	return 0;
}