[白俊]18352号特定の街を探す都市
🙂 質問する
一部の国では1番からN番までの都市とM本の一方通行道路が存在している.すべての道路の距離は1です.
このとき、ある都市Xから、到達可能なすべての都市において、最短距離Kのすべての都市の番号を出力するプログラムが作成される.また、出発都市Xから出発都市Xまでの最短距離は常に0であると仮定する.
例えば、N=4、K=2、X=1の場合、図形は以下のように組織されていると仮定する.
このとき1番都市から行ける都市のうち、最短距離が2の都市は4番都市しかありません.2番と3番の都市については最短距離が1なので出力しません.
😉 に答える
=[0]*(n+1)にアクセス中にエラーが発生しました.
=[-1]*(n+1)にアクセスした場合は正しいです.
どうしてですか.
import sys
from collections import deque
input = sys.stdin.readline
n, m, k, x = map(int, input().split())
graph = [[] for _ in range(n+1)]
for i in range(m):
a,b = map(int, input().split())
graph[a].append(b)
visited = [-1] * (n+1)
def bfs(x):
queue = deque()
queue.append(x)
visited[x] = 0
while queue:
v = queue.popleft()
for i in graph[v]:
if visited[i] == -1:
visited[i] = visited[v] + 1
queue.append(i)
bfs(x)
answer = []
if k not in visited:
print(-1)
else:
for i in range(len(visited)):
if k == visited[i]:
answer.append(i)
answer.sort()
for i in answer:
print(i)Reference
この問題について([白俊]18352号特定の街を探す都市), 我々は、より多くの情報をここで見つけました https://velog.io/@hyesoup/백준-18352번-특정-거리의-도시-찾기テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol