套路题（然而我没看题解做不出来）
题目大意：给你一个$n$个点，$m$条有向边的图。图中有$k$个标记点，求距离最近的标记点间距离。
数据范围：$n,m,k≤10^5$。
设$p_i表$示第$i$个标记点的编号，设$K$为最小正整数，满足$2^K≥k$。
我们在原图中新建点$S$和点$T$，做$2K$次最短路。
对于$K$个二进制位，将$k$个关键点分成两部分，以其中一部分为起点，向另一部分做最短路即可。
时间复杂度：$O(m log n log k)$
1 #include<bits/stdc++.h> 2 #define M 200005 3 #define L long long 4 #define INF (1LL<<60) 5 using namespace std; 6 7 struct edge{L u,v,next;}e[M*2]={0}; L head[M]={0},use=0; 8 void add(L x,L y,L z){use++;e[use].u=y;e[use].v=z;e[use].next=head[x];head[x]=use;} 9 L vis[M]={0},S,T,n,m,k; 10 11 struct node{ 12 L u,dis; node(){u=dis=0;} 13 node(L U,L Dis){u=U; dis=Dis;} 14 friend bool operator <(node a,node b){return a.dis>b.dis;} 15 };priority_queue<node> q; 16 17 L bfs(){ 18 memset(vis,0,sizeof(vis)); 19 q.push(node(S,0)); 20 while(!q.empty()){ 21 node U=q.top(); q.pop(); 22 if(U.u==T) return U.dis; 23 if(vis[U.u]) continue; 24 vis[U.u]=1; 25 for(L i=head[U.u];i;i=e[i].next) 26 if(vis[e[i].u]==0) 27 q.push(node(e[i].u,U.dis+e[i].v)); 28 } 29 return INF; 30 } 31 L u[M]={0},v[M]={0},w[M]={0},id[M]={0}; 32 main(){ 33 scanf("%lld%lld%lld",&n,&m,&k); S=0; T=n+1; 34 for(L i=1;i<=m;i++) scanf("%lld%lld%lld",u+i,v+i,w+i); 35 for(L i=1;i<=k;i++) scanf("%lld",id+i); 36 L ans=INF; 37 for(L p=1;p<=k;p<<=1){ 38 memset(head,0,sizeof(head)); use=0; 39 for(L i=1;i<=m;i++) add(u[i],v[i],w[i]); 40 for(L i=1;i<=k;i++) 41 if(p&i) add(S,id[i],0); 42 else add(id[i],T,0); 43 ans=min(ans,bfs()); 44 45 memset(head,0,sizeof(head)); use=0; 46 for(L i=1;i<=m;i++) add(u[i],v[i],w[i]); 47 for(L i=1;i<=k;i++) 48 if(p&i) add(id[i],T,0); 49 else add(S,id[i],0); 50 ans=min(ans,bfs()); 51 } 52 cout<<ans<<endl; 53 }