比赛 20101224 评测结果 AAAAAAAAAA
题目名称 最佳地点 最终得分 100
用户昵称 王者自由 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2010-12-24 19:43:27
显示代码纯文本
#include <stdio.h>
int fa[500], G[500][500], best;
int main()
{
  FILE *fin, *fout;
  fin = fopen("bestspot.in","rb");
  fout = fopen("bestspot.out","wb");
  int p, f, c;
  fscanf(fin, "%d %d %d\n", &p, &f, &c);
  int a, b, t;
  for(int i=0; i<f; fa[i++]--) fscanf(fin, "%d\n", &fa[i]);
  for(int i=0; i<c; i++) {
    fscanf(fin, "%d %d %d\n", &a, &b, &t);
    G[--a][--b] = t;
    G[b][a] = t;
  }
	for(int i=0; i<p; i++)
		for(int j=0; j<p; j++)
			if(G[j][i])
				for(int k=0; k<p; k++)
					if(G[i][k] && (!G[j][k] || G[j][k]>G[j][i]+G[i][k]))
							G[j][k] = G[j][i]+G[i][k];
	for(int i=0; i<p; i++) G[i][i]=0;
	int good=2000000000;
	for(int i=0; i<p; i++)
	{
		int sum=0;
		for(int j=0; j<f; sum += G[i][fa[j++]]);
		if(good>sum) good = sum, best=i+1;
	}
  fprintf(fout, "%d\n", best);
  fclose(fin); fclose(fout);
  return 0;
}