[白俊(BOJ)]特定距離の都市を探す

質問する

一部の国では1番からN番までの都市とM本の一方通行道路が存在している.すべての道路の距離は1です.
このとき、ある都市Xから、到達可能なすべての都市において、最短距離Kのすべての都市の番号を出力するプログラムが作成される.また、出発都市Xから出発都市Xまでの最短距離は常に0であると仮定する.
例えば、N=4、K=2、X=1の場合、図形は以下のように組織されていると仮定する.

このとき1番都市から行ける都市のうち、最短距離が2の都市は4番都市しかありません.2番と3番の都市については最短距離が1なので出力しません.
入力
1行目は都市の個数N,道路の個数M,距離情報K,出発都市の番号Xを与える.(2≦N≦30000,1≦M≦100000,1≦K≦30000,1≦X≦N)2行目からM行を経て、2つの自然数A,Bをスペース基準で区切る.これは、A番都市からB番都市へ移動する一方通行道路があることを意味する.(1≦A,B≦N)セグメント,AとBは異なる自然数である.

入力

1行目は都市の個数N,道路の個数M,距離情報K,出発都市の番号Xを与える.(2≦N≦30000,1≦M≦100000,1≦K≦30000,1≦X≦N)2行目からM行を経て、2つの自然数A,Bをスペース基準で区切る.これは、A番都市からB番都市へ移動する一方通行道路があることを意味する.(1≦A,B≦N)セグメント,AとBは異なる自然数である.

しゅつりょく

Xから到達可能な都市では最短距離Kの全ての都市の番号が1行ずつ昇順に出力される.
このとき到達可能な都市のうち,最短距離Kの都市が1つも存在しなければ−1を出力する.

I/O例

にゅうしゅつりょく

に答える

これはDFS／BFSアルゴリズムを用いて解決された問題であり,従ってこのリンクでDFS/BFSを学びましょう。
まず,この問題を解決するためにDFSアルゴリズムを用いた.DFSアルゴリズムを用いて距離を格納するのは容易であるようだ.
コードは次のとおりです.

n, m, k, x = map(int, input().split())
arr = [[] for _ in range(n+1)]
distance = [1e9] * (n+1)
distance[x] = 0
length = 1

for _ in range(m):
    idx, city = map(int, input().split())
    arr[idx].append(city)

def dfs(start, length):
    for i in arr[start]:
        distance[i] = min(distance[i], length)
        dfs(i, length + 1)

dfs(x, length)

check = 0
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check += 1
if check == 0:
    print(-1)

上記のコードは、サンプル入力では正しいが、スコアリング時に実行時エラーが発生した.
考えてみれば、到着可能な都市が重複していても、先にアクセスし、距離をmin関数として計算して格納するため、運転速度が遅いという問題がある.
従って,より高速なBFSアルゴリズムを用いて問題を解決することができる.

from collections import deque

n, m, k, x = map(int, input().split())
arr = [[] for _ in range(n+1)]
distance = [-1] * (n+1)
distance[x] = 0

for _ in range(m):
    idx, city = map(int, input().split())
    arr[idx].append(city)

q = deque([x])
while q:
    start = q.popleft()
    for i in arr[start]:
        if distance[i] == -1:
            distance[i] = distance[start] + 1
            q.append(i)

check = 0
for i in range(1, n + 1):
    if distance[i] == k:
        print(i)
        check += 1
if check == 0:
    print(-1)

ポスト

問題を解決できないが、コードを修復する方法が考えられない場合は、大胆に新しい方法で再符号化するのも良い方法のようだ.