[アルゴリズム]白準18352号の特定距離の都市を探す

BFSの概念を利用した大衆的な問題だ.

from collections import deque
import sys
n, m, k, x = map(int, input().split())

graph = [[] for _ in range(n+1)]
for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    graph[start].append(end)




distance = [-1 for _ in range(n+1)]

def bfs(start):
    queue=deque()
    queue.append(start)
    distance[start] = 0
    while queue:
        city = queue.popleft()
        if distance[city] > k:
            break
        for i in graph[city]:
            if distance[i]==-1:
                distance[i] = distance[city]+1
                queue.append(i)

bfs(x)
if k not in distance:
    print(-1)
    sys.exit()
for i in range(len(distance)):
    if k == distance[i]:
        print(i)

大衆的な問題ですが、5回以上タイムアウトを見ていたようで、最初はアルゴリズムが間違っていると思っていました.
理由は,入力を受信する際にinput()を用いただけである.
問題は、最大10,000個のM(パス数)を入力できることです.
時間は2秒に制限されます.
Input()を使用すると、タイムアウトでパスできません.
この問題はずっとinput()を使って解いているので、この点はあまりにも無視されています.
一定量以上の入力はsysです.stdin.readline().第一手()で受け取る.
この点に注意すればBFSアルゴリズムを用いて簡単に解くことができる.
readline()を使用する場合は、readline()の後にrstrip()を追加します.
後の「n」も入力されるので.