记录编号	74588	评测结果	AAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.122 s
提交时间	2013-10-25 21:23:05	内存使用	2.50 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<deque>
#include<vector>
#include<cmath>
using namespace std;
const int SIZEN=801;
const int INF=0x7fffffff;
vector<pair<int,int> > c[SIZEN];//邻接表
int memcow[SIZEN]={0};//农场i有几头牛
int n,m,numcow;
int f[SIZEN][SIZEN]={0};
deque<int> Q;
void SPFA(int s,int d[]){//以s为起点做SPFA,结果存于d
	Q.clear();
	int i,u,v;
	for(i=1;i<=n;i++) d[i]=INF;
	bool inq[SIZEN]={0};//是否在队中(1/0)
	d[s]=0;Q.push_back(s);inq[s]=true;
	while(!Q.empty()){
		u=Q.front();Q.pop_front();inq[u]=false;
		for(i=0;i<c[u].size();i++){
			v=c[u][i].first;
			if(d[v]>d[u]+c[u][i].second){
				d[v]=d[u]+c[u][i].second;
				if(!inq[v]){
					inq[v]=true;
					Q.push_back(v);
				}
			}
		}
	}
}
void make_mindist(void){
	int i;
	for(i=1;i<=n;i++) SPFA(i,f[i]);
}
int sumdist(int x){//糖置于x的路程和
	int i,ans=0;
	for(i=1;i<=n;i++){
		ans+=f[x][i]*memcow[i];
	}
	return ans;
}
int min_sumdist(void){
	int ans=INF;
	for(int i=1;i<=n;i++) ans=min(ans,sumdist(i));
	return ans;
}
void read(void){
	scanf("%d%d%d",&numcow,&n,&m);
	int i,a,b,w;
	for(i=1;i<=numcow;i++){
		scanf("%d",&a);
		memcow[a]++;
	}
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&w);
		c[a].push_back(make_pair(b,w));
		c[b].push_back(make_pair(a,w));
	}
}
int main(){
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout);
	read();
	make_mindist();
	printf("%d\n",min_sumdist());
	return 0;
}