tct_9_4.py

# 이것이 코딩 테스트다 9-4.py
# 실전 문제) 미래 도시

from timeit import default_timer as timer

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

n, m = map(int, input().split())
graph = [[] for _ in range (n + 1)]

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

x, k = map(int, input().split())

start = timer()

def dijkstra(start):
    queue = []
    distance[start] = 0
    heapq.heappush(queue, (0, start))
    while queue:
        dist, current_node = heapq.heappop(queue)
        if distance[current_node] < dist:
            continue
        for connected_node in graph[current_node]:
            cost = distance[current_node] + 1
            if cost < distance[connected_node]:
                distance[connected_node] = cost
                heapq.heappush(queue, (1, connected_node))


answer = 0
distance = [INF] * (n + 1)
dijkstra(1)
answer += distance[k]

distance = [INF] * (n + 1)
dijkstra(k)
answer += distance[x]

end = timer()

if (answer >= INF):
    print(-1)
else:
    print(answer)
print(f"Using Dijkstra Algorithm: {end - start} sec")


# 예시 답안
INF = int(1e9)

# 노드의 개수 및 간선의 개수를 입력받기
n, m = map(int, input().split())

# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자기 자신으로 가는 비용은 0으로 초기화
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를 입력받기
x, k = map(int, input().split())

start = timer()

# 점화식에 따라 플로이드 워셜 알고리즘을 수행
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]

end = timer()

# 도달할 수 없는 경우, -1을 출력
if distance >= INF:
    print(-1)
else:
    print(distance)
print(f"Using Floyd-Warshall Algorithm: {end - start} sec")