문제

풀이

먼저 회사와 도로의 관계는 우리가 아는 그래프의 형태이고 간선은 양방향 이동가능
간선의 비용은 항상 1로 볼 수 있다.
또한 1번회사(노드)에서 k번회사 x번회사로가는 최단거리를 출력해야 하는데
도식화 : 1번 -> k번 -> x번

이는 한 출발지에서 다른 노드의 최단거리를 구하는게 아닌 2개의 출발지에서 다른 노드로가는
최단 거리를 구해야 하므로 다익스트라 알고리즘이 아닌 플로이도 워셜 알고리즘을 사용해야 한다!!!!!

코드

import sys
import time
input = sys.stdin.readline
INF = int(1e9)

V, E = map(int, input().split())

distance = [[INF] * (V+1) for _ in range(V+1)]

for _ in range(E):
  a, b = map(int, input().split())
  distance[a][b] = 1
  distance[b][a] = 1
  
X, K = map(int, input().split())

start = time.time()
for i in range(1, V+1):
  distance[i][i] = 0

#플로이드 워셜알고리즘
for k in range(1, V+1):
  for i in range(1, V+1):
    for j in range(1, V+1):
      distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])


result = 0
result += distance[1][K]
result += distance[X][K]

if(result >= INF):
  print(-1)
else:
  print(result)

end = time.time()
#print(end - start)