记录编号	584736	评测结果	AAAAAAAAAAAA
题目名称	[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	16.209 s
提交时间	2023-11-14 19:17:01	内存使用	26.05 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
#define mp(x,y) make_pair(x,y)
const int N = 5e5+10,M = 8e5+10;
inline ll read(){
    ll x=0;int f=1;
    char ch=getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-')f = -1;
        ch = getchar();
    }
    while(ch >='0' && ch <= '9')x = x * 10 + ch - '0',ch = getchar();
    return x * f;
}
int n,m,t,k;
struct made{
    int ver,nx;ll ed;
}e[M];
int hd[N],tot,a[N];
void add(int x,int y,ll z){
    tot++;
    e[tot].ver = y,e[tot].nx = hd[x],e[tot].ed = z,hd[x] = tot;
}
ll d[N];
bool v[N];
priority_queue<P,vector<P>,greater<P> >q;
void dij(int u){
    memset(d,0x3f,sizeof(d));
    memset(v,0,sizeof(v));
    q.push(mp(0,u));d[u] = 0;
    while(!q.empty()){
        int x = q.top().second;q.pop();
        if(v[x])continue;
        v[x] = 1;
        for(int i = hd[x];i;i = e[i].nx){
            int y = e[i].ver,z = e[i].ed;
            if(d[x] + z < d[y]){
                d[y] = d[x] + z;
                q.push(mp(d[y],y));
            }
        }
    }
}// 
void first(){
    tot = 0;
    memset(hd,0,sizeof(hd));
}
int main(){
    freopen("WAW.in","r",stdin);
    freopen("WAW.out","w",stdout);
    scanf("%d",&t);
    while(t--){
        first();
        n = read();m = read();k = read();
//        scanf("%d%d%d",&n,&m,&k);
        for(int i = 1;i <= m;i++){
            int x,y;ll z;//scanf("%d%d%lld",&x,&y,&z);
            x = read();y = read();z = read();
            add(x,y,z);//单 
        }
        for(int i = 1;i <= k;i++)a[i] = read();//scanf("%d",&a[i]);
        int u = tot;ll ans = ~0ull>>1;
        for(int l = 0;l <= int(log2(n));l++){
            tot = u;hd[0] = 0; 
            for(int i = 1;i <= k;i++){
                if((a[i] >> l) & 1)add(0,a[i],0);
                else add(a[i],n+1,0);
            }
            dij(0); 
            for(int i = 1;i <= k;i++)
                if(((a[i] >> l) & 1) == 0){
                    ans = min(ans,d[a[i]]);
                    hd[a[i]] = e[hd[a[i]]].nx;//把加上的边去掉 
                }
            tot = u;hd[0] = 0;
            for(int i = 1;i <= k;i++){
                if((a[i] >> l) & 1)add(a[i],n+1,0);
                else add(0,a[i],0);
            }
            dij(0);
            for(int i = 1;i <= k;i++)
                if(((a[i] >> l) & 1) == 1){
                    ans = min(ans,d[a[i]]);
                    hd[a[i]] = e[hd[a[i]]].nx;//
                }
        }
        printf("%lld\n",ans);
    }
    
    return 0;
    
}