yamakeeee https://blog.hatena.ne.jp/yamakeeee/ yamake's blog https://yamakeeee.hatenadiary.com/ こどふぉ div. 3 ボス問 div. 3 ボス問解説、すっかりやるのを忘れていましたね。こどふぉの問題は何故か頭に残りにくいので、ちゃんと頭に残すためにも、解き直して（実装はしない）解説をしていくことにしました。 問題概要 頂点 辺の重み付き無向グラフがあります。 個の始点と終点が与えられ、それらの最短経路の総和をコストと呼びます。 辺の重みを にできるときの、コストの最小値を求めなさい。 考えたこと と小さいので、全点対で最短距離が求められるね。 だから消す辺を全探索して、 個の最短距離をそれぞれ求めても間に合いそうだね。 個の最短距離を出すのがちょっと大変かも（？） 解法 上で考えたことをそのまま実装すれば良いです。… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fyamakeeee.hatenadiary.com%2Fentry%2F2021%2F07%2F31%2F121117" title="Codeforces Round #677 - F Reducing Delivery Cost - yamake&#39;s blog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2021-07-31 12:11:17 rich https://yamakeeee.hatenadiary.com/entry/2021/07/31/121117 1.0 100%