7W.2D-최단경로

✏️문제[전보]

import sys
input = sys.stdin.readline

n, m  = map(int, input().split())
INF = 1e9
graph = [[INF]*(n+1) for i 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())

# 1번 회사 -> K번 회사 최단거리 +
# K번 회사 -> X번 회사 최단거리

for m 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][m]+graph[m][b])

if graph[1][k]==INF or graph[k][x] == INF:
  print(-1)
else:
  print(graph[1][k]+graph[k][x])

✏️문제[미래 도시]

INF=int(1e9)

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

for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            matrix[i][j]=min(matrix[i][j], matrix[i][k]+matrix[k][j])

answer=matrix[1][k]+matrix[k][x]
answer=-1 if answer>=INF else answer

print(answer)