[백준] 18352 특정 거리의 도시 찾기 [Python, 파이썬]

• 문제 : https://www.acmicpc.net/problem/18352
• 🔑 다익스트라 알고리즘 사용

 

import sys
from collections import defaultdict
from heapq import heappush, heappop
input = sys.stdin.readline

n, m, k, x = map(int, input().split())  # 도시의 개수, 도로의 개수, 거리 정보, 출발 도시 번호

graph = defaultdict(list)

for i in range(m):
    key, value = map(int, input().split())
    graph[key].append(value)

INF = int(1e9)
dist = [INF] * (n+1)    # 거리 초기화
dist[x] = 0             # 출발지 거리 = 0

q = []
heappush(q, (0, x))     # (거리, 시작점)

while q:
    
    distance, now = heappop(q)

    if distance > dist[now]:               
        continue
    for i in graph[now]:
        if distance + 1 < dist[i]:
            dist[i] = distance + 1
            heappush(q, (distance + 1, i))

sw = 0
for i in range(1, len(dist)):
    if dist[i] == k:
        print(i)
        sw = 1
if sw == 0:
    print(-1)