[Algorithm] 미래도시

INF = int(1e9)

n, m = map(int, input().split())
graph = [[INF] * (n + 1) for _ in range(n + 1)]
# 자기 방향 제외
for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
# 양방향
for _ in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

x, k = map(int, input().split())

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

distance = graph[1][k] + graph[k][x]

if distance >= INF:
    print("-1")
else:
    print(distance)

1번 노드에서 5번 노드를 거쳐 4번노드로 가는 문제이다.
문제만 보면 다익스트라 플로이드나 아무렇게 풀어도 상관없지만 시간복잡도가 널널하기 때문에 더 구현하기 쉬운 플로이드 워셜 알고리즘을 이용해서 구현했다.

거리 그래프를 만드는데 자기자신으로 가는것과 1-2(1->2 2->1) 양방향으로 움직일수있다는점을 고려해 그래프를 만든다.
시작 노드 목표 노드 중간 노드가 모두 고려되는 3차원 for문을 만들고
distance는 무조건 중간노드를 거쳐야하기 때문에
distance = graph[1][k] + graph[k][x] 설정한다.