[백준] 1389 - 케빈 베이컨의 6단계 법칙(설명X)

#include <cstdio>
 
int main() {
    int N, M;
    scanf("%d %d", &N, &M);
    int** arr = new int* [N + 1];
    for (int i = 1; i <= N; i++) {
        arr[i] = new int[N + 1];
        for (int j = 0; j <= N; j++)
            arr[i][j] = 1000000000;
        arr[i][i] = 0;
    }
    for (int i = 0; i < M; i++) {
        int edge1, edge2;
        scanf("%d %d", &edge1, &edge2);
        arr[edge1][edge2] = 1;
        arr[edge2][edge1] = 1;
    }
 
    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            for (int k = 1; k <= N; k++)
                arr[j][k] = arr[j][k] > arr[j][i] + arr[i][k] ? arr[j][i] + arr[i][k] : arr[j][k];
 
    int person = 1, min = 1000000000;
    for (int i = 1; i <= N; i++) {
        int sum = 0;
        for (int j = 1; j <= N; j++)
            sum += arr[i][j];
        if (min > sum) {
            person = i;
            min = sum;
        }
    }
    printf("%d\n", person);
}