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