水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Regular Contest 035:C - アットコーダー王国の交通事情

問題

C - アットコーダー王国の交通事情

全ての頂点が連結であるグラフがあり,この全頂点間の最短距離の和を S とする.「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので,K 回それぞれに対して S を求める問題.

解法

全頂点間について,コストが小さくなった辺を通るときの距離でそれぞれの頂点間の距離の min を取る.その後,S を求めればよい.O((N^3) + (K*(N^2))).

解答

S を min を取るときに同時に求めていてバグらせた.

Submission #3168023 - AtCoder Regular Contest 035

f:id:babcs2035:20180909164738p:plain

gist.github.com