미래도시 : 최단경로

로직 (플로이드 워셜)

1. N,M : 회사수 , 경로수 입력받기
2. graph=[] 2차원리스트 초기화

• 자기자신 -> 자기자신 0으로 초기화
• a,b 입력받으면 1로 초기화

3. x,k : 거쳐갈노드 , 최종목적지노드 입력받기
4. 플로이드워셜 알고리즘 수행
5. 결과 출력

코드

import sys
#input = sys.stdin.readline()

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

# 2 
INF = int(1e9)
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 i in range (m):
  a,b = map(int,(input().split()))
  graph[a][b]=1
  graph[b][a]=1

# 3 잊지않고 입력받아주기
x,k = map(int,input().split())

# 4
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]

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

주의사항

• 플로이드 워셜 알고리즘을 이용
• INF는int(1e9) 를 이용하여 무한으로 정의해주어야함
• distance 거리에 대한 변수를 따로 만들어줘야한다!