
1 17 2 7400 6 7401 7402 7403 7404 7405 7406 7401 6 7412 7402 7400 7406 7410 7411 7402 5 7412 7403 7400 7401 7411 7403 6 7413 7414 7404 7400 7402 7412 7404 5 7403 7414 7415 7405 7400 7405 6 7404 7415 7407 7408 7406 7400 7406 7 7400 7405 7407 7408 7409 7410 7401 7407 4 7408 7406 7405 7415 7408 4 7409 7406 7405 7407 7409 3 7410 7406 7408 7410 4 7411 7401 7406 7409 7411 5 7416 7412 7402 7401 7410 7412 6 7416 7411 7401 7402 7403 7413 7413 3 7412 7403 7414 7414 3 7413 7403 7404 7415 3 7404 7405 7407 7416 2 7411 7412 5 7409 7408 7407 7405 7415 6 7415 7404 7414 7413 7412 7416
4 7400
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int N = 10005;
const int inf = 9999999;
vector<int>mapt[N];
int dis[205][N],nz;
void spfa(int k,int s)
{
queue<int>q;
for(int i=1;i<=nz;i++)
dis[k][i]=inf;
dis[k][s]=1;
q.push(s);
while(!q.empty())
{
s=q.front(); q.pop();
for(int i=0;i<mapt[s].size();i++)
{
int j=mapt[s][i];
if(dis[k][j]>dis[k][s]+1)
{
dis[k][j]=dis[k][s]+1;
q.push(j);
}
}
}
}
int main()
{
int t,id[N],mark[N],go[N],nr,mz,a,kn;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&nz,&nr);
kn=0;
for(int i=1;i<N;i++)
id[i]=0;
for(int i=1;i<=nz;i++)
mapt[i].clear();
for(int i=1;i<=nz;i++)
{
scanf("%d%d",&a,&mz);
if(id[a]==0)
{
kn++; id[a]=kn; mark[kn]=a;//每个块标号,及标号代表的块值
}
int s=id[a];
while(mz--)
{
scanf("%d",&a);
if(id[a]==0)
{
kn++; id[a]=kn; mark[kn]=a;
}
mapt[s].push_back(id[a]);
}
}
kn=0;
while(nr--)
{
scanf("%d",&mz);
while(mz--)
{
scanf("%d",&a);
go[++kn]=id[a];
}
}
for(int i=1;i<=kn;i++)
{
spfa(i,go[i]);
}
int mindis=inf,center;
for(int cid=1;cid<=nz;cid++)
{
int maxdis=0;
for(int i=1;i<=kn;i++)
if(dis[i][cid]>maxdis)
{
maxdis=dis[i][cid];
}
if(maxdis<mindis)
{
mindis=maxdis; center=cid;
}
else if(maxdis==mindis&&mark[center]>mark[cid])
center=cid;
}
printf("%d %d\n",mindis,mark[center]);
}
}
原文:http://blog.csdn.net/u010372095/article/details/45057873