ARC083(ABC074) D Restoring Road Network

問題概要

$N$ 次正方行列 $A$ が与えられる。すべての $u, v$ について、 $A$ の $u$ 行 $v$ 列成分が頂点 $u$ と頂点 $v$ の最短距離となるようなグラフが存在するかを判定する。また、存在する場合、そのようなグラフのうち辺のコストの総和が最小となるものについて、その総和を求めよ。

制約
$1 \le N \le 300$
$i \neq j$ のとき $1 \le A_{i,j} = A_{j,i} \le 10^9$
$i = j$ のとき $A_{i,j} = 0$

解法

実質ワーシャルフロイド(?)

頂点 $i$ から頂点 $j$ に行く最短距離が、頂点 $i$ から頂点 $k$ を経由して頂点 $j$ に行く最短距離よりも長いことはありえない*1、もしそうなっていたら、そのようなグラフは存在しないので-1を出力する
頂点 $i$ から頂点 $j$ に行く最短距離が、頂点 $i$ から頂点 $k$ を経由して頂点 $j$ に行く最短距離と等しいならば、頂点 $i$ と頂点 $j$ の間にある辺は取り除いて良い