白駿18352|特定距離の都市を探す(Dijkstra)

import sys
import heapq

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

# 간선 정보 2차원 리스트에 저장, 
# 모든 도시의 거리는 1 만큼 떨어져있으므로 그래프에 가중치는 1만큼 설정한다.
graph = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append((b, 1))

# 최단 거리 테이블 모두 무한으로 초기화
INF = int(1e9)
distance = [INF] * (n + 1)

# Dijkstra 알고리즘
def dijkstra(start):
    # 시작노드로 가는 최단 경로는 0으로 설정, 힙에 삽입
    distance[start] = 0
    heap = []
    heapq.heappush(heap, (0, start))

    while heap:
        # 최소힙을 이용하여 최단 거리가 가장 짧은 노드 정보 꺼내기
        dist, now = heapq.heappop(heap)

        # 현재 노드가 처리된적이 있다면 무시
        if distance[now] < dist:
            continue

        # 현재 노드와 다른 인접한 노드들을 확인
        for i in graph[now]:
            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(heap, (cost, i[0]))

# 다익스트라 알고리즘을 실행
# x에서 출발하여 n번 도시에 가는데 필요한 최단 거리 테이블 갱신
dijkstra(x)

# 도달할 수 없는 도시 체크를 위한 flag 변수 선언
flag = False

# 최단 경로 테이블을 돌면서 거리가 k인 도시 번호 출력
for i in range(1, n + 1):
    if distance[i] == k:
        flag = True
        print(i)

if flag == False:
    print(-1)