1125:Stockbroker Grapevine

keyword

Warshall-Floyd　C++

概要

有向グラフが与えられる。自分以外のノードへの距離の最大値が最小になるようなノードとその値を求める問題。ノード数は100以下。
ノード数が小さいのでWarshall-Floydが間に合う。

static int g[101][101];
static int dist[101];

int main(){
    int n;
    while( n = readint(), n){
        int i, j, k, m;
        REP(i,n)REP(j,n) g[i][j] = 1<<28;
        REP(i,n){
            m = readint();
            REP(j,m){
                g[i][readint()-1] = readint();
            }
        }

        REP(i,n) g[i][i] = 0;
        REP(k,n)REP(i,n)REP(j,n) g[i][j] = min(g[i][j],g[i][k]+g[k][j]);

        int best = 1<<25, key = 0;
        REP(i,n){
            int ma = *max_element(g[i], g[i]+n);
            if(ma < best){
                best = ma;
                key = i+1;
            }
        }
        if(key) printf("%d %d\n",key, best);
        else printf("disjoint\n");
    }

    return 0;
}