准备投身于ACM的潮流中，失踪人口回归啦！
这个题目的思路还是非常有趣的，因为我们可以注意到，两个可能成为答案兴趣点之间的最短路不应该经过了第三个点，如果经过了，显然和第三个点之间的最短路会更小，则原来的两个点之间不应该成为答案。
考虑到这一点，我们可以想到建枚举每一条边，找到这一条边的两个端点分别最近的兴趣点，一个在正图上，一个在反图上，若二者不同，则这两个距离加上这条边的长度就是可能的答案。
这样我们只要在正反图上分别跑dij，并且记录每个点到达的最近兴趣点是哪个就行。
同时我们要注意到，在跑正反图的时候，需要将所有的兴趣点看作一个集合，以这个集合为起点进行dij，这一个问题可以使用超级源点解决。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#include<ctime>
#include<bitset>
#define int long long
using namespace std;
int t;
int n,m,k;
int p[2];
int head[200005][2];
struct edge{
int to;
int v;
int f;
int ne;
}ed[500005][2];
int dis[500005][2];
int col[500005][2];
int in[500005];
int x,y,z;
void add(int f,int to,int v,int id){
ed[++p[id]][id].to=to;
ed[p[id]][id].f=f;
ed[p[id]][id].ne=head[f][id];
head[f][id]=p[id];
ed[p[id]][id].v=v;
return ;
}
struct st{
int id;
int dis;
friend bool operator <(st x,st y){
return x.dis>y.dis;
}
};
priority_queue<st> q;
int vis[1000005];
void dij(int id){
while(!q.empty()) q.pop();
for(int i=0;i<=n;++i)
dis[i][id]=100000000000000000;
for(int i=1;i<=k;++i){
dis[in[i]][id]=0;
col[in[i]][id]=in[i];
q.push((st){in[i],0});
}
for(int i=1;i<=n;++i)
vis[i]=0;
while(!q.empty()){
st tem=q.top();
q.pop();
if(vis[tem.id]) continue;
vis[tem.id]=1;
for(int i=head[tem.id][id];i;i=ed[i][id].ne){
int to=ed[i][id].to;
if(dis[to][id]>dis[tem.id][id]+ed[i][id].v){
dis[to][id]=dis[tem.id][id]+ed[i][id].v;
col[to][id]=col[tem.id][id];
q.push((st){to,dis[to][id]});
}
}
}
}
signed main(){
scanf("%lld",&t);
while(t--){
memset(head,0,sizeof(head));
p[0]=p[1]=0;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=1;i<=m;++i){
scanf("%lld%lld%lld",&x,&y,&z);
add(x,y,z,0);
add(y,x,z,1);
}
for(int i=1;i<=k;++i){
scanf("%lld",&in[i]);
}
dij(0);
dij(1);
int ans=100000000000000000;
for(int i=1;i<=p[0];++i){
int u=ed[i][0].f;
int v=ed[i][0].to;
if(!col[u][0]||!col[v][1]) continue;
if(col[u][0]==col[v][1]) continue;
ans=min(ans,dis[u][0]+dis[v][1]+ed[i][0].v);
}
printf("%lld\n",ans);
}
return 0;
}