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