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