就我感觉这道题很神仙吗/kel

仔细想想应该也是一种适用范围挺广的做法。

考虑我们可以通过dijkstra在O(nlogn)求出一个点集到另外一个点集的最短路。

那么我们可以通过一些划分点集的方式使得每一对点都被计算一次。

考虑按照二进制划分。

两个不同的数至少有一个二进制位不同。

按照每一个二进制位01分组，跑logn次dijkstra即可得出答案。

#include<bits/stdc++.h>

#define N 220000

#define M 1100000

#define eps 1e-7

#define inf 1e18+7

#define db double

#define ll long long

#define ldb long double

using namespace std;

inline ll read()

{

    char ch=0;

    ll x=0,flag=1;

    while(!isdigit(ch)){ch=getchar();if(ch=='-')flag=-1;}

    while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

    return x*flag;

}

struct edge{ll to,nxt,w;}e[M];

ll num,head[N];

inline void add(ll x,ll y,ll z){e[++num]={y,head[x],z};head[x]=num;}

struct node{ll i,di;};

bool operator<(node a,node b){return a.di>b.di;}

priority_queue<node>q;

ll n,m,k,s,tmp,ans,p[N],dis[N];

void dijkstra()

{

    q.push((node){s,0});dis[s]=0;

    for(ll i=1;i<=n;i++)dis[i]=inf;

    while(!q.empty())

    {

        node k=q.top();q.pop();

        ll x=k.i;if(k.di!=dis[x])continue;

        for(ll i=head[x];i!=-1;i=e[i].nxt)

        {

            ll to=e[i].to;

            if(dis[to]>dis[x]+e[i].w)dis[to]=dis[x]+e[i].w,q.push({to,dis[to]});

        }

    }

}

void work()

{

    n=read();m=read();k=read();ans=inf;

    num=-1;for(int i=0;i<=2*n;i++)head[i]=-1;

    for(ll i=1;i<=m;i++){ll x=read(),y=read(),z=read();add(x,y,z);}

    s=n+1;tmp=num;for(ll i=1;i<=k;i++)p[i]=read();

    for(ll i=0;i<=17;i++)

    {

        for(ll x=1;x<=k;x++)if((1<<i)&p[x])add(s,p[x],0);dijkstra();

        for(ll x=1;x<=k;x++)if(!((1<<i)&p[x]))ans=min(ans,dis[p[x]]);

        head[s]=-1;num=tmp;

        for(ll x=1;x<=k;x++)if(!((1<<i)&p[x]))add(s,p[x],0);dijkstra();

        for(ll x=1;x<=k;x++)if((1<<i)&p[x])ans=min(ans,dis[p[x]]);

        head[s]=-1;num=tmp;

    }

    printf("%lld\n",ans);

}

int main()

{

    int t=read();

    for(int i=1;i<=t;i++)work();

    return 0;

}