记录编号	601118	评测结果	AAAAAAAAAAAA
题目名称	3109.[GXOI/GZOI2019]旅行者	最终得分	100
用户昵称	健康铀	是否通过	通过
代码语言	C++	运行时间	17.883 s
提交时间	2025-06-03 10:05:26	内存使用	12.59 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;
    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();
            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);
                add(x,y,z);
            }
            for(int i = 1;i <= k;i++)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;
        
    }