记录编号	433259	评测结果	AAAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	八级大狂风	是否通过	通过
代码语言	C++	运行时间	0.131 s
提交时间	2017-08-05 09:23:29	内存使用	0.67 MiB

#include <cstdio>
#include <cstring>

#define MAX 10000

int h[MAX],u[MAX],v[MAX],w[MAX],next[MAX];

int head,tail;
int queue[MAX],vis[MAX];

int dis[MAX];
int ans[MAX]={0};
int n,p,c,s,nn[MAX];

int size=0;
void addedge(int x,int y,int z){
	size++;
	u[size]=x;
	v[size]=y;
	w[size]=z;
	next[size]=h[x];
	h[x]=size;
}

void SPFA(int s){
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	memset(queue,0,sizeof(queue));
	head=tail=0;
	dis[s]=0;
	queue[tail++]=s;
	vis[s]=1;
	while(head!=tail){
		int tmp=queue[head++];
		vis[tmp]=0;
		int i;
		for(i=h[tmp];i!=-1;i=next[i]){
			int uu=u[i],vv=v[i],ww=w[i];
			/*if(dis[uu]>dis[vv]+ww){
				dis[uu]=dis[vv]+ww;
				if(!vis[uu]){
					vis[uu]=1;
					queue[tail++]=uu;
				}
			}*/
			if(dis[vv]>dis[uu]+ww){
				dis[vv]=dis[uu]+ww;
				if(!vis[vv]){
					vis[vv]=1;
					queue[tail++]=vv;
				}
			}
		}
	}
	int i;
	for(i=1;i<=p;i++){
		ans[i]+=dis[i];
	}
}

int main(){
	freopen("butter.in","r",stdin);
	freopen("butter.out","w",stdout);
	memset(h,-1,sizeof(h));
	scanf("%d%d%d",&n,&p,&c);
	int i;
	for(i=1;i<=n;i++){
		scanf("%d",&nn[i]);
	}
	for(i=1;i<=c;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		addedge(x,y,z);
		addedge(y,x,z);
	}
	for(i=1;i<=n;i++)
		SPFA(nn[i]);
	int min=0x7f7f7f7f;
	for(i=1;i<=p;i++){
		if(ans[i]<min)
			min=ans[i];
	}
	printf("%d",min);
	return 0;
}