题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6166
题意：给你一个有向图，然后给你k个点，求其中一个点到另一个点的距离的最小值。
解法：枚举二进制位按照标号当前位为1 和当前位为0分为两个集合，每次求解两个集合之间的最短路即可覆盖到所有的点对。时间复杂度20*dijstla时间，这样做的正确性在哪？显然我们需要的答案至少有一个二进制位不同，那么这样求解肯定可以找到正确答案，事实上还可以随机分组emmmm。。。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 100010;
const LL inf = 0x3f3f3f3f3f3f3f3f;
struct edge{
int to,val,next;
}E[maxn];
int head[maxn],edgecnt,a[maxn];
bool vis[maxn];
LL dis[maxn];
void initedge(){
edgecnt=0;
memset(head,-1,sizeof(head));
}
void add(int u, int v, int w){
E[edgecnt].to=v,E[edgecnt].val=w,E[edgecnt].next=head[u],head[u]=edgecnt++;
}
struct node{
int x;
LL step;
node(int x, LL step):x(x),step(step){}
bool operator < (const node &rhs) const{
return step>rhs.step;
}
};
priority_queue<node>q;
LL Dijstra(){
while(!q.empty()){
node now=q.top(); q.pop();
if(vis[now.x]) return now.step;
int u=now.x;
for(int i=head[u]; ~i; i=E[i].next){
int to = E[i].to;
if(dis[to]>dis[u]+E[i].val){
dis[to]=dis[u]+E[i].val;
q.push(node(to,dis[to]));
}
}
}
return inf;
}
void init(){
memset(vis, 0, sizeof(vis));
for(int i=0; i<maxn; i++) dis[i]=inf;
while(!q.empty()) q.pop();
}
LL work(int k)
{
LL ans = inf;
for(int i=0; i<20; i++){
init();
for(int j=1; j<=k; j++){
if(a[j]&(1<<i)){
q.push(node(a[j],0)),dis[a[j]]=0;
}
else{
vis[a[j]]=1;
}
}
ans = min(ans, Dijstra());
init();
for(int j=1; j<=k; j++){
if(a[j]&(1<<i)){
vis[a[j]]=1;
}
else{
q.push(node(a[j],0)),dis[a[j]]=0;
}
}
ans = min(ans, Dijstra());
}
return ans;
}
int T,n,m,k,ks;
int main()
{
ks = 0;
scanf("%d", &T);
while(T--)
{
initedge();
scanf("%d %d",&n,&m);
for(int i=1; i<=m; i++){
int u, v, w;
scanf("%d %d %d", &u,&v,&w);
add(u, v, w);
}
scanf("%d", &k);
for(int i=1; i<=k; i++) scanf("%d", &a[i]);
LL ans = work(k);
printf("Case #%d: %lld\n", ++ks, ans);
}
return 0;
}