因为最后要看的是到所有路线上的区域最大距离最小的中心点，所以可以采取遍历路线上所有的区域，对每个区域进行BFS的办法。为了更方便的在每一次BFS都遍历所有的区域，可以加一个reach数组，记录每个区域被第几站BFS过，进行过一次就将站数赋给reach。BFS时的“距离”类似于”“等距线”，一圈圈的往外面走。
#include <cstdio>
#include <queue>
#include<cstring>
#define ZMAX 10000//定义整个地区编号的最大值
#define INF 100000
using namespace std;
int nz,nr;//number of zones地区数，number of routes路线数
int mz[ZMAX];//存储第i个区域相邻的区域数
int Edge[ZMAX][];//第i个区域相邻的区域的编号
int res[ZMAX];//该区域到所有路线上的区域的距离的最小值
int cur;//“第几站”，用以界定路线上的区域，每次刷新其他区域的res的值
int reach[ZMAX];//记录某个区域res已经刷新到了路线上第几个区域，e.g. reach[s]==cur 表示地区s在第cur+1站已访问
int max(int x,int y)
{
return (x>y)?x:y;
}
void BFS(int s)//从区域s出发的BFS遍历
{
int i,a,b;
int val,at;//val记录层（圈）数（即“等距线”的第几层，或者说是距离），at表示当前节点
queue<int> q[];//滚动队列
a=,b=,val=;
if(reach[s]<cur)//这种情况表示这一站还没刷新过s这个位置
{
q[b].push(s);
reach[s]=cur;
res[s]=max(res[s],val+);//层数是需要+1的，这样才为需要的值
}
while(!q[b].empty())
{
swap(a,b);//开始交换a、b，滚动
val++;//层数+1，因为之前那层的已经全部放入队列中
while(!q[a].empty())
{
at=q[a].front();
q[a].pop();
for(i=;i<mz[at];i++)
{
if(reach[Edge[at][i]]<cur)//看这个的临近区域，未刷新就放入队列
{
q[b].push(Edge[at][i]);
reach[Edge[at][i]]=cur;
res[Edge[at][i]]=max(res[Edge[at][i]],val+);//进行刷新
}
}
}
}
}
int main()
{
int T;
int i,j,t;
int id;
int mr;//公交线路途径区域数
int ret,center;//记录最小星形阈值和中心地区编号
scanf("%d",&T);
for(t=;t<T;t++)
{
memset(reach,-,sizeof(reach));//reach要初始化为1，因为cur初始为0
memset(res,,sizeof(res));
cur=;
scanf("%d%d",&nz,&nr);
for(i=;i<nz;i++)
{
scanf("%d",&id);
scanf("%d",&mz[id]);
for(j=;j<mz[id];j++)
scanf("%d",&Edge[id][j]);
}
for(i=;i<nr;i++)
{
scanf("%d",&mr);
for(j=;j<mr;j++)
{
scanf("%d",&id);
BFS(id);//对公交线路上的每个区域分别进行DFS，刷新其他所有区域的res
cur++;//下一站
}
}
ret=,center=-;
for(i=;i<;i++)
{
if(reach[i]==cur-&&res[i]<ret)//第一条判断是否经过了最后一次的刷新
{
ret=res[i];
center=i;
}
}
printf("%d %d\n",ret,center);
}
return ;
}