ARC083 D: Restoring Road Network
解き方
- これまでに追加した辺のコストの合計と、その辺による各都市間の最短距離(
d[i][j])を保持、更新する - 距離が小さい方から順に考えていく。
町
i, j間の最短距離がcの時、- もし、
d[i][j] == cならば、もう辺を追加する必要はない (A) d[i][j] < cならば、cが最短距離であることに矛盾するので、そのようなグラフはないd[i][j] > cの時、i, j間にコストcの辺を追加する。コストの合計にcを足し、最短距離をd[s][t] = min(d[s][t], d[s][i] + c + d[j][t], d[s][j] + c + d[i][t])で更新する
- もし、
- すべての町のペアに対して行うので、外側のループが
N^2回、内側のコストの更新がO(N^2)なので、全体でO(N^4)の解法となり、N <= 300なので間に合う
その他
- Warshall Floydをしながら、各辺が更新された回数を記録する（2回以上更新された時、その部分は上記解法でいう(A)に当たる）という解法もあり、こっちのほうが綺麗に解けそう
