题意：以任意顶点为起点，能够连通所有的节点，问你以哪个节点为起点时到所有的节点的最短路的最长路最短；
View Code #include#include #include #include #include #include #include #include #include using namespace std;const int inf = 0x7fffffff;int map[124][124],N; int Dij( int start ){ int dis[124],hash[124]; for( int i = 0 ; i <= N ; i ++ ) { dis[i] = inf ; hash[i] = 0; } dis[start] = 0; for( int i = 1 ; i <= N ; i ++ ) { int min = inf ,t; for( int j = 1 ; j <= N ; j ++ ) { if( !hash[j] && min > dis[j] ) { min = dis[j] ; t = j; } } hash[t] = 1; for( int j = 1 ; j<= N ; j ++ ) { if( !hash[j] && map[t][j] != inf && dis[j] > map[t][j] + dis[t] ) dis[j] = dis[t] + map[t][j]; } } int ans = -1; for( int i = 1 ; i <= N ; i++ ) { if( dis[i] > ans ) { ans = dis[i]; // printf( "ans=%d\n",ans ); } } return ans;}void empty( ){ for( int i = 0; i <= N; i ++ ) { for( int j = 0 ; j <= N ; j ++ ) map[i][j] = inf; } }int main( ){ int n,num,T; while( scanf( "%d",&N ),N ) { empty(); for( int i = 1 ; i <= N ; i ++ ) { scanf( "%d",&n ); for( int j = 0 ; j < n ; j++ ) { scanf( "%d %d",&num,&T ); map[i][num] = T; } } int t = 0 , time = inf; for( int i = 1 ; i <= N ; i ++ ) { t = Dij( i ); if( time > t) { num = i ; time = t; } } if( time !=inf ) printf( "%d %d\n",num , time ); else printf( "disjoint\n" ); } //system( "pause" ); return 0;}