題意：
? ? ? 給你n個點，問你在哪里選擇開會地點，使得到所有點的最長路徑最短.

思路： ?n很小，直接Floyd,然后暴力枚舉就行了。

#include<stdio.h>#define INF 100000000int map[110][110];int minn(int a ,int b) {return a < b ? a : b; }void Floyd(int n) {for(int k = 1 ;k <= n ;k ++)for(int i = 1 ;i <= n ;i ++)for(int j = 1 ;j <= n ;j ++)map[i][j] = minn(map[i][j] ,map[i][k] + map[k][j]);}int main () {int n ,i ,j ,nn;int b ,c;while(~scanf("%d" ,&n) && n){for(i = 1 ;i <= n ;i ++)for(j = 1 ;j <= n ;j ++){if(i == j) map[i][j] = 0;else map[i][j] = INF;}for(i = 1 ;i <= n ;i ++){scanf("%d" ,&nn);for(j = 1 ;j <= nn ;j ++){scanf("%d %d" ,&b ,&c);map[i][b] = c;}}Floyd(n);int Min = INF ,mk;for(i = 1 ;i <= n ;i ++){int Max = 0;for(j = 1 ;j <= n ;j ++)if(Max < map[i][j])Max = map[i][j];if(Max != INF && Min > Max){Min = Max;mk = i;}}if(Min == INF) printf("disjoint\n");else printf("%d %d\n" ,mk ,Min);}return 0; }

總結

以上是生活随笔為你收集整理的POJ1125 Floyd的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。