kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_11_C: Breadth First Search

幅優先探索で最短距離を求める問題
今度はたどり着けない頂点には行かなくてよいとのこと

普通に再帰
特に工夫なし
WHITEだとかなんとかもなし
隣接行列じゃなくて隣接リスト

from sys import maxsize

def read_adj():
    n = int(input())
    adj_list = [[] for _ in range(n + 1)]
    for _ in range(1, n + 1):
        u, _, *adj = [int(x) for x in input().split()]
        adj_list[u] = adj
    return n, adj_list

def shortest_paths(n, adj_list, ini_key):
    dist = [maxsize] * (n + 1)

    def visit(key, d):
        dist[key] = d
        d += 1
        for k in adj_list[key]:
            if d < dist[k]:
                visit(k, d)

    visit(ini_key, 0)
    return dist

def print_dist(n, dist):
    for i in range(1, n + 1):
        if dist[i] == maxsize:
            print(i, -1)
        else:
            print(i, dist[i])

def main():
    n, adj_list = read_adj()
    dist = shortest_paths(n, adj_list, 1)
    print_dist(n, dist)

if __name__ == '__main__':
    main()

なんとなく惰性でclass作ってたけどこれくらいなら
作らないほうが楽な気がして今回は素のリスト
素数もlenで取れるけど持ってるから渡したり

再帰を使わないやり方でも書いてみた
割合シンプルにできた模様

def shortest_paths(n, adj_list, ini_key):
    dist = [maxsize] * (n + 1)

    S = [ini_key]
    dist[ini_key] = 0

    while S != []:
        key = S.pop()
        d = dist[key] + 1
        for k in adj_list[key]:
            if d < dist[k]:
                dist[k] = d
                S.append(k)

    return dist