[최단 경로] 백준 18352번: 특정 거리의 도시 찾기 / 실버2

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

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

첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개

www.acmicpc.net

import collections
import heapq
n,m,k,x = map(int, input().split())

graph = collections.defaultdict(list)
for i in range(m):
    u, v = map(int,input().split())
    graph[u].append([v,1])


distance = {}

# time, node
start = [0,x]
q = []
heapq.heappush(q, start)
find = False
while q:
    time, node = heapq.heappop(q)
    if node not in distance:
        distance[node] = time
        if time == k:
            find = True
            print(node)
        if time > k:
            break
        for next, w in graph[node]:
            heapq.heappush(q, [time+w, next])

if not find:
    print(-1)

그냥 다익스트라로 짰다가 시간 초과가 나서 최적화를 했다.

bfs 구현이기 때문에 시간이 k를 넘어서는 시점부터는 탐색을 멈춰도 된다.