BOJ 18352特定距離の都市を検索

acmicpc.net/problem/18352
2秒、256 MBメモリ
input:

都市の個数N、道路の個数M、距離情報K、出発都市の番号X
(2 <= N <= 300,000, 1 <= M <= 1,000,000, 1<= K <= 300,000, 1 <= X <= N)

A B(A番都市からB番都市への一方通行/AはBまでしか行けません.)
output:

最短距離Kのすべての都市番号を昇順で出力します.

最短距離Kの都市がなければ−1を出力する.

一方向道路のグラフィックを表示します.
最短距離を記録する距離リスト、アクセスする距離で表すことができます.
不可能な出発都市が初期化されていないと一度間違えた
input.split()のためタイムアウトが続く
sys.stdin.確かにreadline()を書きます.

from _collections import deque
import sys
N, M, K, X = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
for _ in range(M):
    A, B = map(int, sys.stdin.readline().split())
    graph[A].append(B)

dis = [-1] * (N + 1)
dis[X] = 0
q = deque([X])

while q:
    node = q.popleft()
    for next_node in graph[node]:
        if dis[next_node] == -1:
            dis[next_node] = dis[node] + 1
            q.append(next_node)

check = False
for i in range(1, len(dis)):
    if dis[i] == K:
        print(i)
        check = True

if not check:
    print(-1)