acmicpc.net/problem/18352
시간 2초, 메모리 256MB
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을 출력.
단방향 도로를 나타낼 그래프,
최단 거리를 기록할 distance 리스트, visited는 거리를 이용해서 나타낼 수 있다.
되도 않는 출발 도시 초기화 안 했다가 한 번 틀리고.
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)
