POJ 2139: Six Degrees of Cowvin Bacon

概要

無向グラフが与えられるので，他のすべての頂点への距離の平均が最も小さい頂点を探す．

解法

Warshall-Floydやるだけ．

const int INF = 100000000;
int N, M;
int d[310][310];
int c[310];
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i <= N; ++i) for(int j = 0; j <= N; ++j)
        d[i][j] = i == j ? 0: INF;
    for(int i = 0; i < M; ++i){
        int n;
        scanf("%d", &n);
        for(int j = 0; j < n; ++j) scanf("%d", &c[j]);
        for(int j = 0; j < n; ++j) for(int k = j + 1; k < n; ++k)
            d[c[j]][c[k]] = d[c[k]][c[j]] = 1;
    }
    for(int k=1;k<=N;++k)for(int i=1;i<=N;++i)for(int j=1;j<=N;++j)
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    int res = INF;
    for(int i = 1; i <= N; ++i){
        int tmp = 0;
        for(int j = 1; j <= N; ++j) tmp += d[i][j];
        res = min(res, tmp);
    }
    printf("%d\n", int(res / (N-1.0) * 100 + eps));
    return 0;
}