Codeforces Round #677 - F Reducing Delivery Cost

div. 3 ボス問解説、すっかりやるのを忘れていましたね。こどふぉの問題は何故か頭に残りにくいので、ちゃんと頭に残すためにも、解き直して（実装はしない）解説をしていくことにしました。

$N$ 頂点 $M$ 辺の重み付き無向グラフがあります。 $K$ 個の始点と終点が与えられ、それらの最短経路の総和をコストと呼びます。 $1$ 辺の重みを $0$ にできるときの、コストの最小値を求めなさい。

$N,M \leq 1000$ と小さいので、全点対で最短距離が求められるね。
$M,K\leq 1000$ だから消す辺を全探索して、 $K$ 個の最短距離をそれぞれ求めても間に合いそうだね。 $K$ 個の最短距離を出すのがちょっと大変かも（？）

上で考えたことをそのまま実装すれば良いです。

$K$ 個の最短距離を出すのがちょっと大変かも（？）

は少し複雑で、辺 $\{a,b\}$ を削除したとき、頂点 $u\rightarrow v$ の最短距離の候補は

の三通りあります。
これらを全て調べるとこの問題に答えることができて、時間計算量は $O((N+M)\log(N+M)+MK)$ になります。

yamake's blog