이번 문제는 플로이드-와샬 알고리즘을 통해 해결하였다. 플로이드-와샬 알고리즘을 통해 각 점에서 다른 점까지의 모든 최단 거리를 구하여 리스트를 만들고, 이 리스트에서 모든 경우의 2개의 행을 확인하며 각 점까지의 더 작은 거리의 2배를 더한 값 중 가장 작은 값과 그때의 두 행의 번호를 저장하고 이를 출력하여 해결하였다.

Code

n, m = map(int, input().split())
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    a, b = map(int, input().split())
    grid[a][b] = 1
    grid[b][a] = 1
for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            if i == j:
                 continue
            if grid[i][k] and grid[k][j]:
                if not grid[i][j]:
                    grid[i][j] = grid[i][k]+grid[k][j]
                else:
                    grid[i][j] = min(grid[i][j], grid[i][k]+grid[k][j])
dist, answer = 1e9, []
for i in range(1, n):
    for j in range(i+1, n+1):
        tmp = 0
        for k in range(1, n+1):
            tmp += 2*min(grid[i][k], grid[j][k])
        if dist > tmp:
            answer = [i, j]
            dist = tmp
print(*answer, dist)