玄学优化 : 从AC到75

#include <bits/stdc++.h>
using namespace std;

int p,f,c,sum,ansv = INT_MAX,ans,fav[505],req[505][505];

void readdata()
{
	freopen("in.txt","r",stdin);
	scanf("%d%d%d",&p,&f,&c);
	for (int i = 1;i <= f;i++) scanf("%d",&fav[i]);
	for (int i = 1;i <= p;i++)
	{
		for (int j = 1;j <= p;j++) req[i][j] = 2000;
		req[i][i] = 0;
	}
	for (int i = 1;i <= c;i++)
	{
		int a,b,w;
		scanf("%d%d%d",&a,&b,&w);
		req[a][b] = req[b][a] = w;
	}
}

void floyd()
{
	for (int k = 1;k <= p;k++)
		for (int i = 1;i <= p;i++)
			for (int j = 1;j <= f;j++)
				if (k != i && i != fav[j] && fav[j] != k)
					req[i][fav[j]] = min(req[i][fav[j]],req[i][k] + req[k][fav[j]]);
}

void work()
{
	for (int i = 1;i <= p;i++)
	{
		sum = 0;
		for (int j = 1;j <= f;j++) sum += req[i][fav[j]];
		if (ansv > sum) {ansv = sum; ans = i;}
	}
	printf("%d",ans);
}

int main()
{
	readdata();
	floyd();
	work();
	return 0;
}

for (int j = 1;j <= f;j++)
	if (k != i && i != fav[j] && fav[j] != k)
		req[i][fav[j]] = min(req[i][fav[j]],req[i][k] + req[k][fav[j]]);

for (int j = 1;j <= p;j++)
	if (k != i && i != j && j != k)
		req[i][j] = min(req[i][j],req[i][k] + req[k][j]);

	我以为只枚举其他牧场到Bessie最喜欢的那几个牧场的最短路就可以了,毕竟O(n^3)的Floyd.
	但是这样就WA3个.实在不知道为什么啊...望神犇赐教,不胜感激.

	req数组的初始值应该如何取?为什么要req[i][i] = 0呢?