1.1 题目背景
1949 年，解放前夕北平城内潜伏着许多地下党员。悠酱被任命为地下党指挥官，她希望计算地下党员之间的最小通信距离。
1.2 题目描述
我们不妨将北平城视为由 N 个点和 M 条边组成的无向图，K 名地下党员分布在这些点上 (K ≤ N)。所谓最小通信距离，就是任意两名地下党员间最短路的最小值
1.3 输入格式
第一行一个整数 T，代表数据组数，接下来一共 T 组数据。每组数据第一行为三个整数，N, M, K，分别表示点数、边数、地下党员数。
之后 M 行，每行三个整数，u, v, w，表示 u 和 v 之间有一条长 w 的无向边。之后 1 行，共 K 个整数，表示地下党员所在的结点编号。
1.4 输出格式
输出一共 T 行，每行一个整数，代表最小通信距离。注意如果最小通信距离为 ∞，请输出 −1 代替
数据范围N<=100000,M<=200000,对于所有数据，均保证0<=wi<=1000;
对于暴力，可以直接跑k遍dijkstra，更新答案，实测只有50分。
考虑正解。
假设最后的最优解是x到y之间的最短路，我们发现x与y的二进制表示中至少有一位不同。
于是我们可以枚举每一位，求出在每一位下不同的地下党的最短距离。(我语文不好，说不清）
具体来说，我们可以建一个超级源点s，超级源点t，若地下党点x的第i位为0，则由s向连一条长度为0的边；若为1，则由x向t连一条长度为0的边，以s为起点跑最短路即可。
这样d[t]就表示第i位不同的两地下党点的最短距离，最后取min即可
然而这样会T掉，我们可以把a数组进行离散化，这样枚举的位数就降低到了logk。
连边的时候比较麻烦，因为还要在下一次枚举时删掉，这里有两种解决办法：
1> 记录下刚开始建完图之后的Head数组 与 tot，在更新图时直接将tot赋回原来的值，并将Head数组也赋回原来的值。
2> 我们可以不对图进行修改，直接将第i位为1的数的d[]赋成0，跑最短路后，对第i位为0的数的d[]取min即可。
下面附上代码(其实写了好多不必要的东西）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<queue> #define INF 0x3f3f3f3f #define N 1000010 using namespace std; priority_queue<pair<int,int> >q; int T,n,m,k,Head[N],ver[N*2],nex[N*2],edge[N*2],tot,a[N],b[N],num[N][31],maxn,ss,tt,st,ans,d[N]; int last[N]; bool v[N]; inline int read(){ char c=getchar();int x=0; while(c<'0' || c>'9') c=getchar(); while(c>='0' && c<='9') x=(x<<1)+(x<<3)+c-'0',c=getchar(); return x; } void add(int x,int y,int z){ ver[++tot]=y;edge[tot]=z;nex[tot]=Head[x];Head[x]=tot; } void dijkstra(){ memset(d,0x3f,sizeof(d));memset(v,0,sizeof(v)); d[ss]=0;q.push(make_pair(0,ss)); while(q.size()){ int x=q.top().second;q.pop();if(v[x]) continue;v[x]=1; for(int i=Head[x];i;i=nex[i]){ int y=ver[i],z=edge[i]; if(d[y]>d[x]+z){ d[y]=d[x]+z;q.push(make_pair(-d[y],y)); } } } } void clear(){ memset(Head,0,sizeof(Head));memset(ver,0,sizeof(ver)); memset(nex,0,sizeof(nex));memset(edge,0,sizeof(edge));tot=maxn=0; } int main(){ freopen("underground.in","r",stdin); freopen("underground.out","w",stdout); T=read(); while(T--){ n=read();m=read();k=read();clear();ss=0;tt=n+1;ans=INF; for(int i=1;i<=m;i++){ int u,v,z;u=read(),v=read(),z=read(),add(u,v,z),add(v,u,z); } st=tot; for(int i=1;i<=k;i++) a[i]=read(),last[a[i]]=Head[a[i]]; sort(a+1,a+k+1);int cnt=unique(a+1,a+k+1)-a-1; for(int i=1;i<=k;i++) b[i]=lower_bound(a+1,a+cnt+1,a[i])-a; for(int i=1;i<=k;i++){ int t=b[i],tmp=0; while(t){ num[i][++tmp]=t%2; t/=2;if(t==1){num[i][++tmp]=1;maxn=max(maxn,tmp);break;} } } for(int i=1;i<=maxn;i++){ for(int j=1;j<=k;j++){ if(num[j][i]) add(a[j],tt,0); else add(ss,a[j],0); } dijkstra();ans=min(ans,d[tt]); tot=st;for(int j=1;j<=k;j++) Head[a[j]]=last[a[j]];Head[ss]=Head[tt]=0; } if(ans==INF) printf("-1 "); else printf("%d ",ans); } return 0; }