[백준] 18352번-(Python 파이썬) - Dijkstra

문제링크 : https://www.acmicpc.net/problem/18352

이번 문제도 다익스트라 알고리즘을 이용하여 해결하였다.

문제풀이
1. 출발지점에서 도착지점으로 가는 단방향 그래프 만들기
2. 그래프에서 출발점에서 도착점으로 연결된 점을 이동해주며 최단거리 비용을 dp에 저장한다.
3. dp안에서 원하는 k의 값과 같은 지점을 오름차순으로 출력해준다.
4. 없으면 -1을 출력한다.

import sys
from heapq import heappop, heappush

input = sys.stdin.readline
inf = sys.maxsize

n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n + 1)]
dp = [inf] * (n + 1)
heap = []

def dijkstra(start):
    heappush(heap, [0, start])
    dp[start] = 0
    while heap:
        w, n = heappop(heap)
        for n_n, wei in graph[n]:
            n_w = wei + w
            if n_w < dp[n_n]:
                dp[n_n] = n_w
                heappush(heap, [n_w, n_n])

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

dijkstra(x)
ans = []

for i in range(1, n + 1):
    if dp[i] == k:
        ans.append(i)

if ans:
    for i in ans:
        print(i)
else:
    print(-1)