记录编号	159732	评测结果	AAAAAAAAAAA
题目名称	背驮式行走	最终得分	100
用户昵称	Ra-xp	是否通过	通过
代码语言	C++	运行时间	0.097 s
提交时间	2015-04-22 15:32:12	内存使用	1.84 MiB

#include<iostream>
#include<fstream>
#include<cstring>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<cmath>
#include<cstdio>
#include<queue>
#define MAXN 40000+10
using namespace std;
int b, e, p, n, m;
vector<int> map[MAXN];
long long d[3][MAXN];
int vis[MAXN];
void bfs(int x, int y, int z)
{
	memset(vis, 0, sizeof(vis));
	queue<int> q;
	q.push(z);
	d[y][z]=0;
	vis[z]=1;
	for( ;q.size()>0; )
	{
		int z=q.front();
		q.pop();
		for(int i=0;i<int(map[z].size());i++)
		{
			int v=map[z][i];
			if(!vis[v])
			{
				vis[v]=1;
				q.push(v);
				d[y][v]=d[y][z]+x;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	freopen("piggyback.in","r",stdin);
	freopen("piggyback.out","w",stdout);
	int i, j, k;
	cin>>b>>e>>p>>n>>m;
	for(i=1;i<=m;i++)
	{
		cin>>j>>k;
		map[j].push_back(k);
		map[k].push_back(j);
	}
	bfs(b, 0, 1); bfs(e, 1, 2); bfs(p, 2, n);
	
	long long ret=d[0][n]+d[1][n];
	for(int i=1;i<=n;i++)
	{
		if(ret>d[0][i]+d[1][i]+d[2][i])
		{
			ret=d[0][i]+d[1][i]+d[2][i];
		}
	}
	cout<<ret<<endl;
	return 0;
}