比赛 20101224 评测结果 AAAAAAAAAA
题目名称 最佳地点 最终得分 100
用户昵称 苏轼 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-12-24 19:51:23
显示代码纯文本
#include <fstream>

using namespace std;

int way[502][502];

void floyd(const int n)
{
	int i,j,k;

	for (k=1; k<=n; k++)
		for (i=1; i<=n; i++)
			if (way[i][k])
				for (j=1; j<=n; j++)
					if (way[k][j] && i!=j &&
						(!way[i][j] || way[i][k]+way[k][j]<way[i][j]))
						way[i][j]=way[i][k]+way[k][j];
}

int main(void)
{
	ifstream fin("bestspot.in");
	ofstream fout("bestspot.out");

	int p,f,c;
	fin>>p>>f>>c;

	int fav[502];
	for (int i=0; i<f; i++)
		fin>>fav[i];
	
	int a,b;
	for (int i=0; i<c; i++)
	{
		fin>>a>>b;
		fin>>way[a][b];
		way[b][a]=way[a][b];
	}

	floyd(p);
	
	int minsum=10000000,minans;
	for (int i=1; i<=p; i++)
	{
		int sum=0;
		for (int j=0; j<f; j++)
			if (way[i][fav[j]] || fav[j]==i)
				sum+=way[i][fav[j]];
			else
			{
				sum=10000000;
				break;
			}

		if (sum<minsum)
		{
			minsum=sum;
			minans=i;
		}
	}

	fout<<minans<<endl;

	fin.close();
	fout.close();

	return 0;
}