babcs2035 https://blog.hatena.ne.jp/babcs2035/ きろく https://babcs2035.hateblo.jp/ 競技プログラミング AtCoder その他の問題 問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり，この全頂点間の最短距離の和を S とする．「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので，K 回それぞれに対して S を求める問題． 解法 全頂点間について，コストが小さくなった辺を通るときの距離でそれぞれの頂点間の距離の min を取る．その後，S を求めればよい．O((N^3) + (K*(N^2)))． 解答 S を min を取るときに同時に求めていてバグらせた． Submission #3168023 - AtCoder Regular Conte… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbabcs2035.hateblo.jp%2Fentry%2F2018%2F09%2F09%2F164952" title="AtCoder Regular Contest 035：C - アットコーダー王国の交通事情 - きろく" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/babcs2035/20180909/20180909164738.png Hatena Blog https://hatena.blog 2018-09-09 16:49:52 rich https://babcs2035.hateblo.jp/entry/2018/09/09/164952 1.0 100%