AtCoder BC074 D: Restoring Road Network

問題

https://beta.atcoder.jp/contests/abc074/tasks/arc083_b

解法

ワーシャルフロイド法をベースにしてその考え方を応用することで解けます。

問題を「道路の構造が存在するかどうか」と「存在する道路の長さの和が最小となるようなもの」の二つに分けて考えます。

• 道路の構造が存在するかどうか

表Aが「都市間の道路に沿った最短距離を表した表」なので、表Aに対してワーシャルフロイド法を適用し、表内の値が更新されることがあった場合に表Aは矛盾することになります。

例えば、（iからjへの距離）> （iからkへの距離）+（kからjへの距離）のような場合に、表Aはそもそも矛盾することになります。

よってそのような組み合わせが一つでもあれば、'-1'を出力して終了すれば良いです。

• 存在する道路の長さの和が最小となるようなもの

どのような場合に道路が存在しないといけないかを考えます。

表Aは各都市間の最短経路を表しているので、iからjへの経路を考える場合、

（iからjへの距離）= （iからkへの距離）+（kからjへの距離）

のようなkが存在した場合、k経由で迂回しても距離は変わらないので、iからjへの道路は不要ということになります。

よって、表のサイズと同じ表を用意しておき、道路が必要か不要かをtrue/falseなどで記憶しておき、最後にtrueな経路の距離だけ加算すればよいです。

実装

#include<iostream>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define MOD 1000000007

using namespace std;

typedef long long int ll;

const ll INF=(ll)1e18;

int main(){
    int N;

    cin >> N;

    ll a[N][N];
    bool f[N][N];

    REP(i,N)REP(j,N)cin >> a[i][j];
    REP(i,N)REP(j,N)f[i][j] = true;

    REP(k,N)REP(i,N)REP(j,N){
        if(a[i][k] + a[k][j] < a[i][j]){
            cout << -1 << endl;
            return 0;
        }else if(a[i][k] + a[k][j] == a[i][j] && i != k && k != j){
            f[i][j] = false;
        }
    }

    ll ans = 0;
    REP(i,N)REP(j,N){
        if(f[i][j])ans+=a[i][j];
    }

    cout << ans / 2 << endl;
}