[백준] 18352. 특정 거리의 도시 찾기 (Python)

link 🔗 https://www.acmicpc.net/problem/18352

18352번: 특정 거리의 도시 찾기

 

🔥 기본적인 다익스트라 문제

🔥 다익스트라일까 데이크스트라일까... 뭐가 맞는 것일까...

 

import heapq
import sys

N, M, K, X = map(int, sys.stdin.readline().split())
inf = 2e18
board = [[] for _ in range(N+1)]
result = [inf] * (N+1)

def dijkstra(start):
    result[start] = 0
    heap = []
    heapq.heappush(heap, (0, start)) # 비용, 경유지

    while heap:
        dis, now = heapq.heappop(heap)
        if dis > result[now]:
            continue
        for b in board[now]:
            cost = dis+b[1]
            if cost < result[b[0]]:
                result[b[0]] = cost
                heapq.heappush(heap, (cost, b[0]))

for _ in range(M):
    y, x = map(int, sys.stdin.readline().split())
    board[y].append((x, 1)) # 도착지, 비용

dijkstra(X)

flag = 1

for i in range(1, N+1):
    if result[i] == K:
        flag = 0
        print(i)

if flag:
    print(-1)