记录编号	539719	评测结果	AAAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	6666	是否通过	通过
代码语言	C++	运行时间	2.249 s
提交时间	2019-08-09 16:25:05	内存使用	16.17 MiB

#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
const int maxn=805,INF=0x3f3f3f3f;
int N,P,C,c[maxn],dis[maxn][maxn],ans=INF;
vector<int>v[maxn],w[maxn];
inline void Min(int &x,int y){
	if(x>y)x=y;
}
void Floyd(){
	for(int k=1;k<=P;k++)
	for(int i=1;i<=P;i++)if(i!=k)
	for(int j=1;j<=P;j++)if(i!=j&&j!=k)
		Min(dis[i][j],dis[i][k]+dis[k][j]);
}
struct Q{
	int x,dis;
	bool operator < (const Q &a)const{
		return dis>a.dis;
	}
};
bool vis[maxn];
void Dijkstra(int *dis,int S){
	priority_queue<Q>q;
	while(!q.empty())q.pop();dis[S]=0;
	q.push((Q){S,0});
	memset(vis,0,sizeof(vis));
	while(!q.empty()){
		Q rt=q.top();q.pop();
		if(vis[rt.x])continue;vis[rt.x]=true;
		for(int i=0;i<v[rt.x].size();i++){
			int to=v[rt.x][i];
			if(dis[to]>dis[rt.x]+w[rt.x][i]){
				dis[to]=dis[rt.x]+w[rt.x][i];
				q.push((Q){to,dis[to]});
			}
		}
	}
}
bool bein[maxn];
void Spfa(int *dis,int S){
	queue<int>q;
	while(!q.empty())q.pop();dis[S]=0;
	q.push(S);bein[S]=true;
	while(!q.empty()){
		int rt=q.front();q.pop();bein[rt]=false;
		for(int i=0;i<v[rt].size();i++){
			int to=v[rt][i];
			if(dis[to]>dis[rt]+w[rt][i]){
				dis[to]=dis[rt]+w[rt][i];
				if(!bein[to]){
					bein[to]=true;
					q.push(to);
				}
			}
		}
	}
}
int main(){
	freopen("butter.in","r",stdin);freopen("butter.out","w",stdout);
	scanf("%d%d%d",&N,&P,&C);
	for(int i=1;i<=N;i++){
		int x;scanf("%d",&x);
		c[x]++;
	}
	memset(dis,0x3f,sizeof(dis));
	for(int i=1;i<=P;i++)dis[i][i]=0;
	for(int i=1;i<=C;i++){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		//Min(dis[x][y],z),Min(dis[y][x],z);
		v[x].push_back(y),w[x].push_back(z);
		v[y].push_back(x),w[y].push_back(z);
	}
	//Floyd();
	for(int i=1;i<=P;i++)Dijkstra(dis[i],i);
	for(int i=1;i<=P;i++)Spfa(dis[i],i);
	for(int i=1;i<=P;i++){
		int res=0;
		for(int j=1;j<=P;j++)res+=c[j]*dis[j][i];
		Min(ans,res);
	}
	printf("%d\n",ans);
}