以前の記事で ABC167-D について扱いました。ここで出題された問題は幅優先探索を用いることによって綺麗に解くことができました。今回はほぼ同様の実装で解くことのできる例題を見つけたので扱ってみたいと思います。 問題の概要 $N$ 個の町（町 $1,$ 町 $2…

概要 前回の記事において、単一始点最短経路（Single Source Shortest Path; SSSP）の重みを求めるプログラムである Dijkstra（ダイクストラ）法のpythonによる実装例を紹介しました。そこでは、隣接リストを用いて実装をしましたが、隣接行列を用いても同様…