ARC083 D : Restoring Road Network(500)
作成日：2017.09.17
最終更新日：2017.09.17
問題概要
$N \times N$の表$A$中の整数$A_{i,j}$が$N$個の都市のうち$i$と$j$を結ぶ最短経路の長さとなるように都市間に道路を結ぶ。
道路の長さの総和の最小値を求めよ。
但し、不可能な場合は$-1$と答えよ。
制約
$1 \leq N \leq 300$
$1 \leq A_{i,j} = A_{j,i} \leq 10^9 (i \neq j)$
$A_{i,i} = 0$
考え方
まず不可能な場合を考える。
都市$i,j$間の最短距離は$A_{i,j}$なので、$i,j$間にその長さの道路があると考えて良い。
この時、全点対間最短経路を求めて値が変わるものがあれば不可能であることが分かる。
逆に値が変わらなければ、少なくともこの道路の結び方では可能あることが分かる。
また、これはワーシャルフロイド法を用いることで$O(N^3)$で判定できる。
次に可能な時の解を求めることを考える。
都市$i,j$間に長さが$A_{i,j}$でない道路がある時、その長さは最短距離の条件から$A_{i,j}$より長い必要がある。
しかし都市$i,j$を経由する最短経路では$i,j$間を$A_{i,j}$で結ぶ経路の方が必ず採用されるので、そのような道路は不要である。
したがって、都市$i,j$を結ぶ道路は存在するならば長さが$A_{i,j}$である必要がある。
あとは各道路が必要であるかを判定できれば良い。
ある道路が必要なのはその道路が存在しないことでその道路が結ぶ都市間の最短距離が大きくなってしまう時である。
これは別の都市を経由する経路で距離が$A_{i,j}$以下となるものが存在しないことと同じである。
これを調べるのは各都市$i,j$の組において$O(N)$で可能である。
以上の方法の計算量は$O(N^3)$であるから十分高速である。
ソースコード
マクロ等はこちら
const int MC = 303;
int N;
int A[MC][MC];
int B[MC][MC];
LL ans;
int main(){
cin >> N;
repp(i,0,N){
repp(j,0,N){
cin >> A[i][j];
B[i][j] = A[i][j];
if(i < j) ans += A[i][j];
}
}
repp(k,0,N) repp(i,0,N) repp(j,0,N) B[i][j] = min(B[i][j] , B[i][k] + B[k][j]);
repp(i,0,N) repp(j,i+1,N){
if(A[i][j] != B[i][j]){
cout << -1 << endl;
return 0;
}
repp(k,0,N){
if(k == i || k == j) continue;
if(A[i][j] == A[i][k] + A[k][j]){
ans -= A[i][j];
k = N;
}
}
}
cout << ans << endl;
return 0;
}解法まとめ
道路の構成が可能かどうかはワーシャルフロイド法を用いて調べる。
最短距離が更新されていたら不可能である。(16,18-21行)
都市$i,j$間に道路が必要か否かは別の都市$k$を経由する経路で距離が$A_{i,j}$となるものが存在するかで判定する。(22-28行)