(ワーシャルフロイド)POJ-2139-Six Degrees of Cowvin Bacon

問題URL→http://poj.org/problem?id=2139

自分以外の全ての役者との距離の平均の最小値を求める。
N<=300なのでワーシャルフロイドできる。

//#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#define FOR(i,bg,ed) for(ll i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
#define MOD 1000000007
#define int long long
using namespace std;
typedef long long ll;
typedef vector<vector<ll>> mat;
const int INF = 1e9;
//typedef pair<int, int> P;
typedef pair<double, double> P;

const int MAX_V = 310;
int d[MAX_V][MAX_V];

int N, M;
int num;
int a[310];

signed main()
{
    cin >> N >> M;

    REP(i,N) REP(j,N) {
        if (i == j) d[i][j] = 0;
        else d[i][j] = INF;
    }

    REP(i,M) {
        cin >> num;
        REP(j,num) {
            cin >> a[j];
            a[j]–;
        }

        REP(j,num) REP(k,num) {
            if (j == k) continue;
            else d[a[j]][a[k]] = 1;
        }
    }

    REP(k,N) REP(i,N) REP(j,N) {
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
    }

    int mi = INF;
    REP(i,N) {
        int sum = 0;
        REP(j,N) {
            if (i == j) continue;
            sum += d[i][j];
        }
        mi = min(mi, sum);
    }

    cout << mi * 100 / (N – 1) << endl;
}