미래 도시

 

 

유형 파악

이 문제는 간단하다. a에서 b 그리고 b에서 c로의 이동을 다뤘다.

즉, 모든 경로에 대한 최단 경로가 필요하므로 최단 경로 알고리즘 중에서도 플로이드 워셜 알고리즘을 사용한다.

특징 적으로 3단 반복문을 사용하면 된다.

 

 

코드

 

n, m = map(int, input().split())
INF = 1e9
graph = [[INF]*(n+1) for _ in range(n+1)]
for i in range(m):
    a, b = map(int, input().split())
    graph[a][b] = 1
    graph[b][a] = 1
x, k = map(int, input().split())

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


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

print(graph[1][k] + graph[k][x])