题意:有n个人每个人可以把谣言传给一些人,传给每个人有一定的时间,求出你把谣言传给谁,让所有的人都知道的时间最短。
思路:枚举每个点为起点,到所有点的距离的最大值就是该点为起点所消耗的时间,求出最小值就可以了,因为给的n较小,直接 floyd就可以了。。
#include<stdio.h> #include<string.h> const int N=110; const int inf=0x3fffffff; int dis[N],vis[N],n,map[N][N]; int main() { int i,m,t,j,k,min,max; while(scanf("%d",&n),n) { for(i=1;i<=n;i++) { for(j=i+1;j<=n;j++) map[i][j]=map[j][i]=inf; map[i][i]=0; } for(i=1;i<=n;i++) { scanf("%d",&m); while(m--) { scanf("%d%d",&j,&t); if(map[i][j]>t) map[i][j]=t; } } for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(map[i][j]>map[i][k]+map[k][j]) map[i][j]=map[i][k]+map[k][j]; min=inf;k=-1; for(i=1;i<=n;i++) { max=-1; for(j=1;j<=n;j++) { if(map[i][j]>max) max=map[i][j]; } if(min>max){min=max;k=i;} } if(min<inf)printf("%d %d\n",k,min); else printf("disjoint\n"); } return 0; }