ABC074 D - Restoring Road Network
解法
まずは、答えが-1、つまり入力された値で条件を満たすグラフを作成できるかどうかの判定をします。
これは、ワーシャルフロイド法を用いて行うことができます。行った結果、すべての距離が更新されることがなかった場合、条件を満たすグラフを作成することができます。
続いて、道路の距離の和を求めます。小さい方から、貪欲に決めていきます。
まずは、全ての種類の辺を、つながっている2つの頂点と共に一つの配列に格納します。そして、辺の距離の昇順でソートを行います。
あとは、前から見ていきます。イメージはエラトステネスの篩です。
まずは、一番小さい距離の辺を取り出します。これは確定で使うことになりますので、答えの合計値に加えておきます。
この辺が、iとjを繋いでいるものだったとすると、i,j以外の頂点kを持ってきたときに、
(iとjの距離)+(jとkの距離) = (iとkの距離)
であったとき、頂点iとkの辺をカウントしてしまうと、ダブりが発生します。ので、iとkの辺を配列から取り出した場合に距離の合計に加えないようにフラグを立てておきます。
この操作を、右辺が(jとkの距離)の場合も含めて、kについて全探索します。
この操作が終わったら、辺を格納した配列の次の要素を見ます。それが先ほどフラグを立てた辺でない場合は今と同じ操作を、立てた辺であれば操作を何も行わずにスキップをします。
これを、全ての辺について行っていきます。
これを繰り返すことで、最終的な辺の距離の和が求まります。
