提交记录

#include<bits/stdc++.h>
using namespace std;
int n, P, c, x, y, z, cnt, minn = 0x3f3f3f3f;
int p[810 * 4], h[810 * 4], dis[810 * 4];
bool inq[810 * 4];
queue<int>q;
struct node{
	int ne;
	int to;
	int w;
}f[810 * 4];
void add(int x, int y, int z){
	f[++cnt].ne = h[x];
	h[x] = cnt;
	f[cnt].to = y;
	f[cnt].w = z;
}
void spfa(int x){
	memset(inq, false, sizeof(inq));
	for(int i = 1; i <= n; i++){
		dis[i] = 0x3f3f3f3f;
	}
	dis[x] = 0;
	q.push(x);
	inq[x] = true;
	while(!q.empty()){
		int qf = q.front();
		q.pop();
		inq[qf] = false;
		for(int i = h[qf]; i; i = f[i].ne){
			if(dis[f[i].to] > dis[qf] + f[i].w){
				dis[f[i].to] = dis[qf] + f[i].w;
				if(inq[f[i].to] == false){
					inq[f[i].to] = true;
					q.push(f[i].to);
				}
			}
		}
	}
}
int main(){
	scanf("%d%d%d", &n, &P, &c);
	for(int i = 1; i <= n; i++){
		scanf("%d", &p[i]);
	}
	for(int i = 1; i <= c; i++){
		scanf("%d%d%d", &x, &y, &z);
		add(x, y, z);
		add(y, x, z);
	}
	for(int i = 1; i <= P; i++){
		spfa(i);
		int sum = 0;
		for(int j = 1; j <= n; j++){
			sum += dis[p[j]];
		}
		minn = min(minn, sum);
	}
	printf("%d", minn);
	return 0;
}