D - Restoring Road Network - AtCoder Regular Contest 083
隣接行列形式でN都市間の距離が与えられる。この隣接行列で表された距離が最短距離となるようなN都市間の経路グラフは構成できるか？できるならば、経路の長さの和が最短であるようなものの経路の和を求めよ。
隣接行列に対してWarshall Froydで最短性の確認を行う。この時、ある経路について行列要素が更新された場合、最短路とならない。
逆に最短路であった場合、Warshall Froydの中で、各(i, j)に対し、d[i][j] == d[i][k] + d[k][j] という条件を満たした回数をカウントしておく。この回数が3以上であった場合、あるiともjとも異なるkが存在して、d[i][j] == d[i][k] + d[k][j] を満たしていることがわかる。これは別の経路を通ってiからjに最短路でいけるということを示しており、(i, j)間の直通経路は削除しても良い。そのため、このカウントが2であるような要素について、経路の長さの和をとってやればよい。O(V^3)。
(カウントが1は対角線にしか出てこない。また0がないのはWarshall Froydの最短路になっていることから明らか)
