记录编号	396031	评测结果	AAAAAAAAAAA
题目名称	[USACO 3.2] 香甜的黄油	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	2.717 s
提交时间	2017-04-17 21:14:59	内存使用	2.82 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 810, INF = 0x7fffffff;

inline int in(void){ 
	char tmp = getchar();
	int res = 0;
	while(!isdigit(tmp))tmp = getchar();
	while(isdigit(tmp))
		res = (res + (res << 2) << 1) + (tmp ^ 48),
		tmp = getchar();
	return res;
}

int N, P, C;
int dis[MAXN][MAXN];
int cow[MAXN], ans = INF;

int main(){ 
#ifndef LOCAL
	freopen("butter.in", "r", stdin);
	freopen("butter.out", "w", stdout);
#else
	freopen("test.in", "r", stdin);
#endif
	memset(dis, 0x7f / 3, sizeof(dis));

	N = in(), P = in(), C = in();
	for(int i = 1; i <= N; ++i)cow[i] = in();
	for(int i = 0; i <= P; ++i)dis[i][i] = 0;
	for(int i = 1, a, b; i <= C; ++i){ 
		a = in(), b = in();
		dis[a][b] = dis[b][a] = min(dis[a][b], in());
	}

	for(int k = 1; k <= P; ++k){ 
		for(int i = 1; i <= P; ++i){ 
			for(int j = 1; j <= P; ++j){ 
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}

	for(int i = 1, tmp = 0; i <= P; ++i, tmp = 0){ 
		for(int j = 1; j <= N; ++j){ 
			tmp +=dis[i][cow[j]];
		}

		ans = min(ans, tmp);
	}
	printf("%d\n", ans);

	return 0;
}