AtCoder ABC074 D - Restoring Road Network
問題
解法
判定すべき問いは「表が本当に最短距離を示しているか?」です。
これは「ワーシャルフロイド法」を用いると、判定できます。
また、問いがYesの場合には、必要な道路の総距離(の最小値)を求めます。
ワーシャルフロイド法って?
ワーシャルフロイド法は、点i - j 間の最短距離を求めるアルゴリズムです。
実際には、「点i → j と行くよりも、点i → k → j と行くほうが早くないか?」という問いを、
kに全ての点を代入し判定します(早い場合は早い方の距離に更新します)。
今回の問題では、入力の表に対してワーシャルフロイド法を行い、
元の表と変化がない場合はYes(ちゃんと最短距離を示していた)、ある場合はNoとなります。
必要な道路の総距離は?
全ての点同士に道路を設ければ、表の通りになりますが、求める最小値にはなりません。
なくても構わない道路とはどんなものでしょうか?
不要な道路とは、点i - j 直通の道路がなくても表の距離で行ける道路です。
(逆に、必要な道路とは、その道路がないと最短距離が変わってしまう道路です。)
(「入力例 3」の点1 - 2間の道路は、点1 → 4 → 2 の道路で同じ距離で行けるので不要です。)
(「入力例 3」の点1 - 3間の道路は、どう迂回しようが直接1 → 3 に行くより遅くなるので必要です。)
これを全ての2点間の道路に対して判定して、必要な道路の距離の和を求めます。
実装
#include <bits/stdc++.h> using namespace std; typedef vector<int> vi; typedef vector<vi> vvi; #define rep(i, n) for (int i = 0; i < (int)(n); i++) #define print(x) cout << x << endl bool f(vvi v) { vvi tmp = v; int n = v[0].size(); rep(k, n)rep(i, n)rep(j, n) { // 経由点kは必ず一番外側のループ v[i][j] = min(v[i][j], v[i][k] + v[k][j]); } bool ok = true; rep(i, n)rep(j, n) { if (v[i][j] != tmp[i][j]) ok = false; } return ok; } ll f2(vvi v) { ll res = 0; int n = v[0].size(); rep(i, n)rep(j, n) { bool nokosu = true; rep(k, n) { if (k == i || k == j) continue; if (v[i][j] >= v[i][k] + v[k][j]) nokosu = false; } if (nokosu) res += v[i][j]; } return res; } int main(void){ int n; cin >> n; vvi v(n, vi(n)); rep(i, n)rep(j, n) cin >> v[i][j]; bool ok = f(v); if (ok) { // 点i-jと点j-iを二重に判定してるので割る2 ll res = f2(v) / 2; print(res); } else { print(-1); } }