この問題はプライオリティーキューを使うことで \(O((N+M)\log (N+M))\) で解くことができます。

どのように操作を進めても、各頂点を消すために必要なコストは増えないので、どの時点についても、「現時点で必要なことが確定しているコスト」以下のコストで消せる頂点は消してしまっても良いことがわかります。したがって、「現時点でコストが最も低い頂点に対して操作を行う」を \(N\) 回繰り返すのが最適であることがわかります。

「現時点でコストが最も低い頂点」を愚直に求めると \(\Omega(N)\) の計算量がかかり、全体で \(\Omega(N^2)\) となってしまいますが、ダイクストラ法のように、プライオリティーキューを用いて差分更新を行うことにより全体で \(O((N+M)\log (N+M))\) で求めることができます。

実装例(C++)