白俊解答-特定距離の都市を探す18352号

8758 ワード
幅優先ナビゲーション ダエストラ グラフィック理論 グラフィックの参照 テキストリンク
📜 問題を理解する
一部の国では1番からN番までの都市とM本の一方通行道路が存在している.すべての道路の距離は1です.
このとき、ある都市Xから、到達可能なすべての都市において、最短距離Kのすべての都市の番号を出力するプログラムが作成される.また、出発都市Xから出発都市Xまでの最短距離は常に0であると仮定する.
例えば、N=4、K=2、X=1の場合、図形は以下のように組織されていると仮定する.
このとき1番都市から行ける都市のうち、最短距離が2の都市は4番都市しかありません.2番と3番の都市については最短距離が1なので出力しません.
💡 問題の再定義
方向図にx個のノードのうち最短距離kのすべてのノードを出力する
▼▼▼計画作成
最小生成ツリーを使用して問題を解決します.
最小生成ツリーをkまで拡張します.
その後、kを超えると、繰り返し文を停止し、すべてのkのノードを出力する.
💻 計画の実行
import sys

distance = []
adj_list = []
node_state = []


if __name__ == '__main__':
    N, M, K, X = map(int, sys.stdin.readline().split())
    d = 0
    adj_list = [[] for _ in range(N + 1)]
    distance = [300001 for _ in range(N + 1)]
    node_state = ['U' for _ in range(N + 1)]
    result = []

    for _ in range(M):
        city1, city2 = map(int, sys.stdin.readline().split())
        adj_list[city1].append(city2)

    node_state[X] = 'T'
    distance[X] = d
    for adj_node in adj_list[X]:
        node_state[adj_node] = 'F'

    while 'F' in node_state:
        d += 1
        if d > K:
            break
        fringe_node = []
        for i, state in enumerate(node_state):
            if state == 'F':
                fringe_node.append(i)
        for node in fringe_node:
            node_state[node] = 'T'
            distance[node] = d
            if d == K:
                result.append(node)
            for adj_node in adj_list[node]:
                if node_state[adj_node] == 'U':
                    node_state[adj_node] = 'F'

    if not result:
        print(-1)
    else:
        print(*result, sep='\n')
🤔 振り返る
最短距離アルゴリズムを知ってこそ解決できる問題.
最小生成木を用いずに複数の曲線を用いて解くことも可能である.
100のプロジェクト56 -反応Popovicラジオ
PhoneGap API紹介:デバイス