미래 도시

 

풀이법

이 문제는 최소 이동 경로를 찾아야해서 플로이드 알고리즘으로 풀어야 한다. 모든 회사 사이의 가중치는 1이며 양방향 연결로 구성되어 있다. graph 이중 리스트를 만들고 이 안에 자기 자신으로 향하는 방향은 0을 넣어줬다. 그리고 삼중 배열로 최단 거리를 구해주면 된다.

 

코드

INF = int(1e9)

n, m = map(int, input().split())

graph = [[INF] * (n+1) for i in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1, n+1):
    graph[i][i] = 0

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)

안보고 풀어서 로직은 다 맞았는데 어이없게도 n, m의 위치를 바꿔쓰고 x, k의 위치도 바꿔써서 처음에 답이 나오지 않았다.