[白俊]18352号特定の街を探す都市

最短パスで問題を検索
input=sys.stdin.readlineを行わない場合、2%はタイムアウトを継続します.

import heapq
import sys
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 i in range(m):
    a,b=map(int,input().split())
    graph[a].append((b,1))

def dijackstra(start):
    q=[]
    heapq.heappush(q,(0,start))
    distance[start]=0
    while q:
        dist,now=heapq.heappop(q)
        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(q,(cost,i[0]))

dijackstra(x)
answer=[]

for i in range(n+1):
    if distance[i]==k:
        answer.append(i)

if answer:
    for x in answer:
        print(x)
else:
    print(-1)