Namaran

Code daily. Without assist.

2026-10-28

Walks.hs

edges :: [(Int, Int, Int)]
edges = [(0, 1, 1), (1, 2, -2), (2, 1, 1)]

step :: [Int] -> [Int]
step ds = [minimum (ds !! v : [ds !! u + w | (u, t, w) <- edges, t == v]) | v <- [0 .. 2]]

main :: IO ()
main = print (iterate step [0, 1000000, 1000000] !! 1000)

これは何を出力するでしょうか?

Answer

[0,-498,-500] です。

edges の (u, t, w) は、頂点 u から頂点 t へ重み w で進める辺です。step は各頂点 v について、いまの値 ds !! v と、v に入る辺ごとの ds !! u + w のうち最小のものを新しい値にします。新しい値はどれも前の回のリスト ds だけから計算するので、1回の step で辺を1本ずつ伸ばす形になります。

1000回を順に追う代わりに、k 回目のあとの値が何を表しているかを考えます。辺を順にたどる道筋(同じ頂点を何度通ってもよい)の重みの合計を道筋の長さと呼ぶと、k 回目のあとの ds !! v は、頂点0から v へ辺を k 本以下使って行く道筋の長さの最小値です。0回目は頂点0が辺0本の0で、ほかは道筋がまだ無い印の1000000です。k + 1 本以下の道筋は、k 本以下で済んでいるか、k 本以下で u まで来て最後に辺 (u, v, w) を足したものなので、step の最小値がちょうどその最小値になります。1000000から作った値は、本物の道筋が見つかるとすぐに負けるので、答えには残りません。

頂点0に入る辺は無いので、頂点0は0のままです。頂点1へは、辺 (0, 1, 1) の1本で長さ1、そこから1→2→1と回るたびに辺が2本増えて長さが -2 + 1 で1ずつ減ります。辺を1000本まで使えるので、1 + 2 * 499 の999本で回れるのは499周で、最小値は 1 - 499 の -498 です。頂点2へは0→1→2の2本で長さ -1、同じく 2 + 2 * 499 の1000本で499周できるので -500 になります。

頂点の数より1回少ない2回で値が決まると考えると、2回目の [0,1,-1] と答えてしまいます1。1→2→1の閉路は長さが -1 なので、回るほど値は下がり続け、決まった値に落ち着くことはありません。それでも1000回で止めれば、使える辺の本数で周回の数が決まり、値は1つに決まります。

  1. 辺を1本ずつ伸ばしながら最小値を更新するこの手順は、ベルマン・フォード法(Bellman-Ford algorithm)です。頂点が n 個で長さが負になる閉路が無ければ、同じ頂点を2度通らない道筋で足りるので、n - 1 回で値が決まります。