【POJ】1125 Stockbroker Grapevine

题目大意是要找出从一个结点到其他所有结点总共所花时间的最小值，所以可以采用Floyd算法求出每个结点到其他结点的最短路径，之后找到每个结点花的最长时间，再找到最小值即可：

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 110;
const int INF = 9999;

int dis[N][N];

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 ++ ){
    
                if(i != j && dis[i][j] > dis[i][k] + dis[k][j]){
    
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }
}

int main(){
    
    int n, m;
    while(cin >> n && n){
    
        memset(dis, INF, sizeof(dis));
        for(int i = 1; i <= n; i ++ ){
    
            cin >> m;
            while(m -- ){
    
                int to, length;
                cin >> to >> length;
                dis[i][to] = length;
            }
        }
        Floyd(n);
        int minimum = INF;
        int node;
        for(int i = 1; i <= n; i ++ ){
    
            int maximum = 0;
            for(int j = 1; j <= n; j ++ ){
    
                if(i != j && maximum < dis[i][j]) maximum = dis[i][j];
            }
            if(minimum > maximum){
    
                minimum = maximum;
                node = i;
            }
        }
        if(minimum < INF) cout << node << " " << minimum << endl;
        else cout << "disjoint" << endl;
    }
    return 0;
}