题意：给定无向图，Alice在A集合选一个点，Bob在B集合选一个点，CXK在全集里选择一个点。 然后问“三人到某一点集合打篮球的最小距离”的期望。

思路：做过一个裸题，就是给定三人位置，问去哪里集合距离代价最小。 那题就是三个点跑三次SPFA，就可以更新答案了。而此题有一个Cxk，非常的头疼，然而注意到边权为1，tm的不是直接BFS扩展就可以了吗。枚举Alice和Bob的位置，然后dis[i]=disA[i]+disB[j]，然后就可以扩展了。 注意不要带log就可以过这题了，排序可以用基数排序，然后维护两个单调队列，每次取小的一个队首进行扩展。

#include
#define ll long long
#define rep(i,a,b) for(int i=a;i<=b;i++) using namespace std; const int maxn=; const int inf=1e9; int disA[][maxn],disB[][maxn],a[maxn],b[maxn]; int Laxt[maxn],Next[maxn],To[maxn],cnt,N; ll sum; void add(int u,int v) { Next[++cnt]=Laxt[u]; Laxt[u]=cnt; To[cnt]=v; } void BFS(int dis[],int st) { rep(i,,N) dis[i]=inf; dis[st]=; queueq; q.push(st);
while(!q.empty()){
int u=q.front(); q.pop();
for(int i=Laxt[u];i;i=Next[i]){
if(dis[To[i]]==inf){
dis[To[i]]=dis[u]+;
q.push(To[i]);
}
}
}
}
int num[maxn],c[maxn],dis[maxn];
void solve() //基数排序+两个单调队列
{
rep(i,,N+N) num[i]=;
rep(i,,N) num[dis[i]]++,d[i]=;
rep(i,,N+N) num[i]+=num[i-];
rep(i,,N) c[num[dis[i]]--]=i;
queueq1,q2;
rep(i,,N) q1.push(c[i]);
while(!q1.empty()||!q2.empty()){
if(q2.empty()||(!q1.empty()&&!q2.empty()&&dis[q1.front()]dis[u]+) {
dis[To[i]]=dis[u]+;
q2.push(To[i]);
}
}
}
else {
int u=q2.front(); q2.pop();
for(int i=Laxt[u];i;i=Next[i]) {
if(dis[To[i]]>dis[u]+) {
dis[To[i]]=dis[u]+;
q2.push(To[i]);
}
}
}
}
rep(i,,N) sum+=dis[i];
}
int main()
{
int C=,T,M,A,B,u,v;
scanf("%d",&T);
while(T--){
scanf("%d%d",&N,&M);
rep(i,,N) Laxt[i]=; cnt=;
rep(i,,M){
scanf("%d%d",&u,&v);
add(u,v); add(v,u);
}
scanf("%d",&A); rep(i,,A) scanf("%d",&a[i]);
scanf("%d",&B); rep(i,,B) scanf("%d",&b[i]);
rep(i,,A) BFS(disA[i],a[i]);
rep(i,,B) BFS(disB[i],b[i]);
sum=;
rep(i,,A)
rep(j,,B){
rep(k,,N) dis[k]=disA[i][k]+disB[j][k];
solve();
}
ll ans=1LL*A*B*N;
ll g=__gcd(ans,sum);
printf("Case #%d: ",++C);
if(g==sum) printf("%lld\n",sum/g);
else printf("%lld/%lld\n",sum/g,ans/g);
}
return ;
}