ALDS1_11_C: Breadth First Search (続き)

解説を読む
むー
キューを使うのかー

いやちょっと待て
キューだろうがスタックだろうが結果はいっしょではなかろうか

スタックを使うと厳密には幅優先にならないとか？
あるか

ということでキューに書き換える
dequeを使えば瞬殺

from collections import deque

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

    S = deque()
    S.append(ini_key)
    dist[ini_key] = 0

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

    return dist

名前がそれっぽくないので今ひとつピンとこないですね

にも通じるけど
popleftをpopとかappendをappendleftとか間違っちゃうと
一発でスタックになってしまうという

あと
WHITEとかGRAYとかフラグ立てて管理するの、いまだにわからない
初めて到着したらGRAYになるから、もうそれが最短と決めつけてることになるけど
1回目に訪問したときは実は遠回りで別ルートで到着したときのほうが最短になるかもしれないじゃない？
幅優先だからそういうのないはず、ってことかもしれないけど
それを保証っていうか証明しないといけないし（いけなくはないけど
フラグ立てて管理するより、このまま訪問しても最短にならない場合は訪問しない、って
考えたほうが素直な気がするんだけどなあ
処理の回数も増えないと思うし
フラグで書くほうがちょっとだけ判定が速いかもしれないけど