记录编号	562702	评测结果	AAAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	真的好烦	是否通过	通过
代码语言	C++	运行时间	0.538 s
提交时间	2021-07-09 11:25:10	内存使用	1.87 MiB

#include<bits/stdc++.h>
using namespace std;
const int N=805,M=1455*2;
int head[N],e[M],nxt[M],w[M],idx=0,d[N];
int c[N],cnt,n,m;
bool inq[N];
void addedge(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	nxt[idx]=head[a];
	head[a]=idx++;
}
int spfa(int u)
{
    
	memset(d,0x3f,sizeof(d));
	d[u]=0;
	queue<int> q;
	q.push(u);
	inq[u]=true;
	while(q.size())
	{
		int x=q.front();
		q.pop();
		inq[x]=false;
		for(int i=head[x];i!=-1;i=nxt[i])
		{
			int y=e[i],z=w[i];
			if(d[y]>d[x]+z)
			{
				d[y]=d[x]+z;
				if(!inq[y])
				{
					q.push(y);
					inq[y]=true;
				}
			}
		}
	}
	int tot=0;
	for(int i=1;i<=n;i++) tot+=(d[i]*c[i]);
	return tot;
} 
int main()
{
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout);
	memset(head,-1,sizeof(head));
	cin>>cnt>>n>>m;
	for(int i=0;i<cnt;i++)
	{
		int a;
		cin>>a;
		c[a]++;
	}
	while(m--)
	{
		int a,b,c;
		cin>>a>>b>>c;
		addedge(a,b,c);
		addedge(b,a,c);
    } 
    int ans=0x7fffffff;
    for(int i=1;i<=n;i++) ans=min(ans,spfa(i));
    cout<<ans;
	return 0;
}