kb84tkhrのブログ

何を書こうか考え中です あ、あと組織とは関係ないってやつです 個人的なやつ

ALDS1_12_B: Single Source Shortest Path I

始点を決めて、そこからの最短経路を求める問題
Single Source Shortest Path IってことはあとでIIが出てくるってことだな
きっとIでは素直に書けばOKってことだろう

素直に書いた(自分なりに
始点から初めて、隣の頂点までの距離がそれまでの最短記録を更新している隣を探索し続ける

続きを読む

ALDS1_12_A: Minimum Spanning Tree (続き2)

どうやって動いてるのかと言うと

頂点0をMSTのルートとする
頂点0の周りの頂点への暫定最短距離を記録していく

暫定最短距離が一番小さい頂点をMSTに含める
その頂点の周りの頂点への暫定最短距離を更新していく
全部の頂点がMSTに含まれるまで売り返す

て感じか
暫定を覚えておく分処理が少なくて済むってわけだな
あと、最短になりそうなところからやっていく分ムダな努力も少なくて済みそう

続きを読む

ALDS1_12_A: Minimum Spanning Tree (続き2)

解説を読む
なぜこのアルゴリズムで正しいのかは書いてないな
そこまで書いてたらボリュームがすごいことになるってことだろう

このアルゴリズムを実装するポイントは、辺の選択ステップで"どのように最小の重みをもつ辺を保存しておくか"です。

そこだなきっと

続きを読む