比赛 20101224 评测结果 WWWWWWWWWW
题目名称 最佳地点 最终得分 0
用户昵称 wangwangdog 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-12-24 19:40:53
显示代码纯文本
#include<stdio.h>
long i,j,k,n,m,f,best[501],map[501][501],min,d[501][501],a,b,dis,minp;
int main()
{
	FILE *fin,*fout;
	fin=fopen("bestspot.in","rb");
	fout=fopen("bestspot.out","wb");
	fscanf(fin,"%ld%ld%ld\n",&n,&f,&m);
	for(i=1;i<=f;i++)
	{
		fscanf(fin,"%ld\n",&best[i]);
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
		{
			map[i][j]=2100000000;
			d[i][j]=2100000000;
		}
	
	for(i=1;i<=m;i++)
	{
		fscanf(fin,"%ld%ld%ld\n",&a,&b,&dis);
		map[a][b]=dis;
		map[b][a]=dis;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			d[i][j]=map[i][j];
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=n;j++)
			{
				if(d[i][k]+d[k][j]<d[i][j])d[i][j]=d[i][k]+d[k][j];
			}
		}
	}
	
	min=2100000000;
	minp=0;
	for(i=1;i<=n;i++)
		d[i][i]=0;
	for(i=1;i<=n;i++)
	{int o=0;
		for(j=1;j<=f;j++)
			o=o+d[i][best[j]];
		if(o<min){min=o;minp=i;}
	}
	fprintf(fout,"%ld",minp);
	fclose(fin);
	fclose(fout);
	return 0;
}