今回は幅優先探索です。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
- 作者: 渡部有隆,Ozy(協力),秋葉拓哉(協力)
- 出版社/メーカー: マイナビ
- 発売日: 2015/01/30
- メディア: 単行本(ソフトカバー)
- この商品を含むブログ (7件) を見る
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_11_C
ポイントは time = t[now-1]+1ってところでしょうか。
from collections import deque n = int(input()) V=[] # info = deque([]) t = [(1<<12) for _ in range(n)] time = 0 for i in range(n): info = deque(list(map(int,input().split()))[2:]) V.append(info) def bfs(u): global time queue = deque([]) queue.append(u) t[u-1] = time while len(queue)!=0: now = queue.popleft() time = t[now-1]+1 while len(V[now-1])!=0: nb =V[now-1].popleft() if time < t[nb-1]: queue.append(nb) t[nb-1] = time bfs(1) for i,time in enumerate(t): if time == (1<<12): time = -1 print(i+1,time)
本日のおまけ
どうもこんにちは、NewDaysの回し者です。
嘘です。よしねの魅力を伝える30秒動画です。