题目大意：$n$ 个点$m$ 条边的有向图中，给定$k$ 个点，问这$k$ 个点两两间的最短路的最小值。
Dijkstra
因为题目要求的是两两不同点间的最短路，故可以将这k个点划分成两个集合，一个连接虚起点，另一个连接虚终点，求起点到终点的最短路即可。
如何划分？看到群里有人是用随机化划分过的，除了随机化还有一种靠谱的放法。
枚举二进制的每一位，将这$k$ 个数分成两个集合，这种做法保证了每两个点至少被分到两个集合一次。
复杂度$O(nlog^2n)$ 。
代码如下：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
struct edge{
int t,w;
edge(int T,int W){t=T;w=W;}
};
struct node{
int v,d;
node(int V,int D){v=V;d=D;}
friend bool operator<(node a,node b){
return a.d>b.d;
}
};
const int N=100005;
const int inf=1e9;
vector<edge>e[N];
int vis[N],dis[N],adj[N][3];
priority_queue<node>q;
int dijkstra(int s,int t){
while(!q.empty())q.pop();
memset(vis,0,sizeof(vis));
for(int i=s;i<=t;++i)dis[i]=inf;
dis[s]=0;
q.push(node(s,0));
while(!q.empty()){
node t=q.top();q.pop();
int u=t.v;
if(vis[u])continue;
vis[u]=1;
for(int i=0;i<(int)e[u].size();++i){
int v=e[u][i].t,w=e[u][i].w;
dis[v]=min(dis[u]+w,dis[v]);
if(!vis[v])q.push(node(v,dis[v]));
}
}
return dis[t];
}
int T,n,m,k,a[N];
int main(void){
scanf("%d",&T);
for(int t=1;t<=T;++t){
int ans=inf;
scanf("%d%d",&n,&m);
for(int i=0;i<m;++i)
for(int j=0;j<3;++j)
scanf("%d",&adj[i][j]);
scanf("%d",&k);
for(int i=0;i<k;++i)
scanf("%d",&a[i]);
for(int i=0;i<20;++i){
for(int op=0;op<2;++op){
for(int j=0;j<=n+1;++j)e[j].clear();
for(int j=0;j<m;++j)e[adj[j][0]].push_back(edge(adj[j][1],adj[j][2]));
for(int j=0;j<k;++j){
if(((a[j]>>i)&1)==op)e[0].push_back(edge(a[j],0));
else e[a[j]].push_back(edge(n+1,0));
}
ans=min(ans,dijkstra(0,n+1));
}
}
printf("Case #%d: %d\n",t,ans);
}
}