记录编号	584716	评测结果	AAAAAAAAAAAA
题目名称	[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	1.887 s
提交时间	2023-11-14 17:50:07	内存使用	33.07 MiB

#include <bits/stdc++.h>
#define LL long long
using namespace std;
inline LL read(){
    LL x = 0,f = 1; char c = getchar();
    while (c != EOF && !isdigit(c)) {if (c == '-') f = -1;c = getchar();}
    while (isdigit(c)) {x = x * 10 + c - '0';c = getchar();}
    return x * f;
}
inline void write(LL x){
    if (x < 0) putchar('-'),x = -x;
    if (x > 9) write(x/10); putchar(x%10+'0');
}
inline void writeln(LL x){ write(x),putchar('\n'); }

const int N = 100005,M = 500005;
int Fr[M<<2],To[M<<2],Ne[M<<2],Dis[M<<2],He1[N],He2[N],_k;
inline void add(int *He,int x,int y,int z){
	++_k,Fr[_k] = x,To[_k] = y,Dis[_k] = z,Ne[_k] = He[x],He[x] = _k;
}

int T,n,m,k,p[N];

const LL INF = 1ll<<60;

int f1[N],f2[N];
LL dis1[N],dis2[N];

struct Node{
	int x; LL d;
	Node (int xx = 0,LL dd = 0){ x = xx,d = dd; }
	inline bool operator < (Node x) const{ return d > x.d; }
}t;

priority_queue<Node>Heap;



void Dij_1(){ //dis1 : p[i] -> x
	int i;
	while (!Heap.empty()) Heap.pop();
	for (i = 1; i <= n; ++i) dis1[i] = INF,f1[i] = -1;
	for (i = 1; i <= k; ++i) dis1[p[i]] = 0,f1[p[i]] = p[i],Heap.push(Node(p[i],0));
	int p,x;
	while (!Heap.empty()){
		t = Heap.top(); Heap.pop();
		if (t.d == dis1[t.x])
		for (p = He1[t.x]; p ; p = Ne[p]) if (dis1[To[p]] > dis1[t.x] + Dis[p]){
			dis1[To[p]] = dis1[t.x] + Dis[p];
			f1[To[p]] = f1[t.x];
			Heap.push(Node(To[p],dis1[To[p]]));
		}
	}
}

void Dij_2(){ //dis2 : x -> p[i]
	int i;
	for (i = 1; i <= n; ++i) dis2[i] = INF,f2[i] = -1;
	for (i = 1; i <= k; ++i) dis2[p[i]] = 0,f2[p[i]] = p[i],Heap.push(Node(p[i],0));
	int p,x;
	while (!Heap.empty()){
		t = Heap.top(); Heap.pop();
		if (t.d == dis2[t.x])
		for (p = He2[t.x]; p ; p = Ne[p]) if (dis2[To[p]] > dis2[t.x] + Dis[p]){
			dis2[To[p]] = dis2[t.x] + Dis[p];
			f2[To[p]] = f2[t.x];
			Heap.push(Node(To[p],dis2[To[p]]));
		}
	}
}

LL ans;
int main(){
	freopen("WAW.in","r",stdin);
	freopen("WAW.out","w",stdout);
	int i,u,v,w;
	T = read();
	while (T--){
		_k = 0;
		memset(He1,0,sizeof(He1));
		memset(He2,0,sizeof(He2));
		
		n = read(),m = read(),k = read();
		while (m--){ u = read(),v = read(),w = read(); if (u^v) add(He1,u,v,w),add(He2,v,u,w); }
		for (i = 1; i <= k; ++i) p[i] = read();
		Dij_1();
		Dij_2();
		ans = INF;
		for (i = 1; i <= n; ++i) if (f1[i] ^ f2[i]) ans = min(ans,dis1[i] + dis2[i]);
		for (i = 1; i <= _k; i += 2) if (f1[Fr[i]]^f2[To[i]])
			ans = min(ans,dis1[Fr[i]] + dis2[To[i]] + Dis[i]);
		writeln(ans);
	}
    return 0;
}