题目链接
题目大意一个有n个点的图中，求一个点，使得这个点到其他点的最短路的最长距离最短。
输入数据中，有多组测试。每组测试第一行为n，接下来n行，每行第一个x，xi表示第i个点和x个点有路径。接下来x个数对a,b表示i到a的代价为b
最后输出这个点和最长距离。
这道题是显而易见的最短路了。但是我们发现这个题的起点不确定。所以不是单源最短路，不能用SPFA
这里介绍另外一种算法：floyd算法。
floyd算法主要解决的是多源最短路问题，范围比SPFA更广，但时间复杂度是O(n^3)。再看题目n≤100，符合条件。
floyd算法，简而言之，就是找i,j两个点，然后找一个中间点k，如果i->k+k->j的最短路径比当前i->j更短，就更新i->j的最短路。
代码如下:
for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]>f[i][k]+f[k][j])//f存i->j的最短路{f[i][j]=f[i][k]+f[k][j];}}}}最后统计答案时，对于每一个点i，看看它到其他点的最短路的最大值。这样，这道题的代码就呼之欲出了。
参考代码 #include<cstdio>#include<cstdlib>#include<cstring>int n;int f[105][105];int main(){while(1){scanf("%d",&n);if(n==0)break;memset(f,63,sizeof(f));for(int i=1;i<=n;i++){f[i][i]=0;int x;scanf("%d",&x);for(int j=1;j<=x;j++){int soy1,soy2;scanf("%d %d",&soy1,&soy2);f[i][soy1]=soy2;}}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if(f[i][j]>f[i][k]+f[k][j]){f[i][j]=f[i][k]+f[k][j];}}}}/*for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)printf("%d ",f[i][j]>10000?-1:f[i][j]);printf("\n");}*/int ans=2147483647,ans2=-1;for(int i=1;i<=n;i++){int tt=-1;for(int j=1;j<=n;j++){if(f[i][j]>999999){tt=-1;break;}if(f[i][j]>tt)tt=f[i][j];}if(tt!=-1 && tt<ans){ans=tt;ans2=i;}}if(ans2==-1)printf("disjoint\n");else printf("%d %d\n",ans2,ans);}return 0;} View Code
转载于:https://www.cnblogs.com/AFOer-lhy/p/7826007.html
