记录编号	616399	评测结果	AAAAAAAAAAA
题目名称	309.[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	栖云渡	是否通过	通过
代码语言	C++	运行时间	1.005 s
提交时间	2026-06-19 12:08:25	内存使用	5.79 MiB

#include<iostream>
using namespace std;
const int maxn=805;
const int inf=0x3f3f3f3f;
int n,p,c,ans=inf;
int id[maxn];
int d[maxn][maxn],f[maxn][maxn];
int main()
{
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout); 
	cin>>n>>p>>c;
	for(int i=1;i<=n;i++)cin>>id[i];
	for(int i=1;i<=p;i++)for(int j=1;j<=p;j++)d[i][j]=inf;
	for(int i=1;i<=c;i++){
		int x,y,z;
		cin>>x>>y>>z;
		d[x][y]=d[y][x]=z;
	}
	for(int i=1;i<=p;i++)d[i][i]=0;
	for(int i=1;i<=p;i++)for(int j=1;j<=p;j++)f[i][j]=d[i][j];
	//Floyd!!
	for(int k=1;k<=p;k++){
		for(int i=1;i<=p;i++){
			for(int j=1;j<i;j++){
				if(f[i][j]>f[i][k]+f[k][j]){
					f[i][j]=f[i][k]+f[k][j];
					f[j][i]=f[i][j];
				}
			}
		}
	}
	for(int k=1;k<=p;k++){//settle down in k
		int temp=0;
		for(int i=1;i<=n;i++){
			temp+=f[id[i]][k];
		}
		if(ans>temp){
			ans=temp;
		}
	}
	cout<<ans<<endl;
	return 0;
}