1389번: 케빈 베이컨의 6단계 법칙

https://www.acmicpc.net/problem/1389


$O(m+n^3)$

#include<cstdio>
int n, m, c[101][101], r, mini = 1e9;
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) c[i][j] = (i != j)*1e9;
    for (int i = 0, x, y; i< m; i++)scanf("%d %d", &x, &y), c[x][y] = c[y][x] = 1;
    for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)for (int k = 1; k <= n; k++) if (c[j][i] + c[i][k] < c[j][k])c[j][k] = c[j][i] + c[i][k];
    for (int i = 1; i <= n; i++) {
        int s = 0;
        for (int j = 1; j <= n; j++) s += c[i][j];
        if (s < mini)mini = s, r = i;
    }
    printf("%d", r);
    return 0;
}