[백준 18352번] 특정 거리의 도시 찾기

Dijkstra 최단 경로 알고리즘 사용

import sys
import heapq

input=sys.stdin.readline

INF=int(1e9)

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

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

for _ in range(m):
    a, b= map(int, input().split())
    # a에서 부터 b까지 가는 거리는 1
    graph[a].append((b, 1))

def dijkstra(start):
    q = []

    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        else:
            for i in graph[now]:
                cost = dist + i[1]
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))

dijkstra(x)

flag=0

for i in range(1, n+1):
    if distance[i]==k:
        flag+=1
        print(i)

if flag==0:
    print(-1)