ゆる〜くpythonの練習「幅優先探索編」

今回は幅優先探索です。

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

問題はこちら。
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秒動画です。