Senior Pan fails in his discrete math exam again. So he asks Master ZKC to give him graph theory problems everyday.
The task is simple : ZKC will give Pan a directed graph every time, and selects some nodes from that graph, you can calculate the minimum distance of every pair of nodes chosen in these nodes and now ZKC only cares about the minimum among them. That is still too hard for poor Pan, so he asks you for help.
Input
The first line contains one integer T, represents the number of Test Cases.1≤T≤5.Then T Test Cases, for each Test Cases, the first line contains two integers n,m representing the number of nodes and the number of edges.1≤n,m≤100000
Then m lines follow. Each line contains three integers xi,yixi,yi representing an edge, and vivi representing its length.1≤xi,yixi,yi≤n,1≤vivi≤100000
Then one line contains one integer K, the number of nodes that Master Dong selects out.1≤K≤n
The following line contains K unique integers aiai, the nodes that Master Dong selects out.1≤aiai≤n,aiai!=aj
Output
For every Test Case, output one integer: the answer
Sample Input
1 5 6 1 2 1 2 3 3 3 1 3 2 5 1 2 4 2 4 3 1 3 1 3 5
Sample Output
Case #1: 2
题意：给你一个无向图，然后给你K个数字，然后让你求任意两点之间的最短距离，并输出这些最短距离的最小值；
题解：首先考虑最短路径的算法，Foyld肯定不行O（n^3）;Dijkstra与SPFA都是O（nlog(n)）。然后由于K的范围是10^5级别的
如果暴力跑Dijkstra的话 n*(n+1)/2次。。。。 我们可以考虑二进制，任意两个数字至少有一位是不同的，所以我们枚举每一位上不同的点（也就17次就够了），将其分别放入两个集合，建立超级源点（0），和超级汇点（n+1）,分别将两个集合与超级源点和超级汇点相连，距离为0，这样Dijkstra的单源多汇最短路就变为了，多源多汇最短路了，然后用优先队列优化的Dijkstra跑最短路即可，也就17*2次,O(nlog(n)),时间复杂度满足要求；
参考代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL INF=0x3f3f3f3f3f3f3f3fLL;
const int maxn=1e5+10;
int n,m,k,tot;
int u[maxn],v[maxn],vis[maxn],head[maxn],num[maxn];
LL w[maxn],dis[maxn];
struct Edge{
int u,v;
LL w;
Edge(int uu,int vv,LL ww) : u(uu),v(vv),w(ww) { }
};
vector<Edge> vec[maxn];
struct Node{
int id;
LL W;
bool operator < (const Node &b) const
{
return W>b.W;
}
};
void addedge(int u,int v,LL w)
{
vec[u].push_back(Edge(u,v,w));
}
priority_queue<Node> q;
LL Dijkstra()
{
memset(vis,0,sizeof vis);
memset(dis,INF,sizeof dis);
dis[0]=0;
q.push(Node{0,0} );
while(!q.empty())
{
Node u=q.top(); q.pop();
int Id=u.id;
if(vis[Id]) continue;
vis[Id]=1;
for(int i=0;i<vec[Id].size();i++)
{
if(!vis[vec[Id][i].v] && dis[vec[Id][i].v]>dis[Id]+vec[Id][i].w)
{
dis[vec[Id][i].v]=dis[Id]+vec[Id][i].w;
q.push(Node{vec[Id][i].v,dis[vec[Id][i].v]});
}
}
}
return dis[n+1];
}
void Init()
{
tot=0;
memset(head,-1,sizeof head);
for(int i=0;i<=n+1;i++) vec[i].clear();
}
int main()
{
int Cas=0,T;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++) scanf("%d%d%lld",u+i,v+i,w+i);
scanf("%d",&k);
for(int i=1;i<=k;i++) scanf("%d",num+i);
LL ans=INF;
for(int bit=0;bit<=17;bit++)
{
Init();
for(int i=1;i<=m;i++) addedge(u[i],v[i],w[i]);
for(int i=1;i<=k;i++)
{
if(num[i]&(1<<bit)) addedge(0,num[i],0);
else addedge(num[i],n+1,0);
}
ans=min(ans,Dijkstra());
Init();
for(int i=1;i<=m;i++) addedge(u[i],v[i],w[i]);
for(int i=1;i<=k;i++)
{
if((num[i]&(1<<bit))==0) addedge(0,num[i],0);
else addedge(num[i],n+1,0);
}
ans=min(ans,Dijkstra());
}
printf("Case #%d: %lld
",++Cas,ans);
}
return 0;
}