记录编号	131258	评测结果	AAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2014-10-24 08:19:29	内存使用	5.22 MiB

#include<iostream> 
#include<queue>
#include<cstdio>
#include<cstring>
using namespace std;
int dx[801][801]={0},dis[801],b[801][801]={0};
int niu[801],minn=0x7fffffff;
int n,p,c;
void spfa(int);
int main()
{
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout);
	ios::sync_with_stdio(false);
	cin>>n>>p>>c;
	for(int i=1;i<=n;i++) cin>>niu[i];
	for(int i=1;i<=c;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		dx[x][y]=dx[y][x]=z;
		b[x][++b[x][0]]=y;
		b[y][++b[y][0]]=x;
	}
	for(int i=1;i<=p;i++)
	{
		int sum=0;
		spfa(i);
		for(int j=1;j<=n;j++) sum+=dis[niu[j]];
		if(sum<minn) minn=sum;
	}
	cout<<minn;
	return 0;
}
void spfa(int x)
{
	bool f[801]={0};
	memset(dis,0x7f,sizeof(dis));
	queue<int> q;
	dis[x]=0;
	q.push(x);
	f[x]=1;
	while(!q.empty())
	{
		int k=q.front();
		for(int i=1;i<=b[k][0];i++)
		{
			if(dx[k][b[k][i]]>0 && dis[b[k][i]]>dis[k]+dx[k][b[k][i]])
			{
				dis[b[k][i]]=dis[k]+dx[k][b[k][i]];
				if(!f[b[k][i]])
				{
					q.push(b[k][i]);
					f[b[k][i]]=1;
				}
			}
		}
		f[k]=0;
		q.pop();
	}
}