Livedoorブログからの移動
はてなブログからの移動

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)に当たる）という解法もあり、こっちのほうが綺麗に解けそう

github.com