ありよりのあり

\主に競プロ備忘録/

D - Restoring Road Network

問題概要

N個のノードのグラフの全点間最短距離A_ijが与えられる.
これを満たすような辺の張り方は存在するか.あるなら辺のコストの総和を求めよ.
1 <= N <= 300, 1 <= A_ij <= 109

解法

各頂点間について,A_ijの辺があるか,辺が存在しないかのいずれかである.
A_ijを元にWarshall Floydで全点間最短距離B_ijを求める.
A_ij != B_ijなら条件を満たすグラフは存在しない.
次に条件を満たすグラフが存在するとして,その間に辺があるか存在しないかを判定する.
辺が存在しない <-> 迂回路が存在する
ということであるから,迂回する頂点kとして
a[i][j] = a[i][k] + a[k][j] であれば,辺が存在しない.
そうでないような辺を全て足して出力する.

メモ

各辺について毎回Dijkstraをする解法が思いついたがこれだと間に合わず.
union-findを使って連結でなければ無条件で辺を足し,連結でないならばDijkstraで辺が必要か判定,とやるとギリギリ間に合った.

想定解法のような柔軟な解法が出したい.
辺の存在が迂回路で確かめられることは覚えておこう.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 302;

using PP = pair<ll,P>;

ll a[MAX_N][MAX_N],b[MAX_N][MAX_N];

int main(){
  int N;
  cin >> N;
  rep(i,N) rep(j,N) scanf("%lld",&a[i][j]);
  bool conf = true;
  rep(i,N) conf &= (a[i][i]==0LL);
  rep(i,N-1) REP(j,i+1,N) conf &= (a[i][j]==a[j][i]);
  if(!conf){
    cout << "-1" << endl;
    return 0;
  }
  rep(i,N) rep(j,N) b[i][j] = a[i][j];
  rep(i,N) rep(j,N) rep(k,N) b[i][j] = b[j][i] = min(b[i][j],b[i][k]+b[j][k]);
  ll ans = 0LL;
  rep(i,N-1) REP(j,i+1,N){
    if(b[i][j]!=a[i][j]){
      cout << "-1" << endl;
      return 0;
    }else{
      bool pls = true;
      rep(k,N){
        if(k==j||k==i) continue;
        // 迂回路が存在するか?
        pls &= (b[i][k]+b[k][j]!=b[i][j]);
      }
      if(pls) ans += b[i][j];
    }
  }
  cout << ans << endl;
  return 0;
}