ARC083 D問題 Restoring Road Network

問題

AtCoder Regular Contest 083 - AtCoder

解説

入力例のケースで考えてみます。

3
0 1 3
1 0 1
3 1 0

この場合三角形の頂点に３つの街があると仮定し、辺の付近に都市間の距離を書いた、図は

     3
  ①ーー③
1｜　 ／ 
  ②／ 1

となります。

しかし都市間の距離を長さだと考えると、このような三角形は作ることはできません。 それは 辺の長さをa, b, cとすると、a + b < c からです。 よってこのようなケースが存在すれば入力例のような道路の構造はありえないので出力は-1となります。

では道路の構造が存在する場合について考えてみます。与えられるのは全都市間を結んだケースです。 以下のケースで考えてみます。

3
0 1 3
1 0 2
3 2 0

図に表すと

     3
  ①ーー③
1｜　 ／ 
  ②／ 2

このようになります。
ここで総距離が最小で全ての都市が繋がっていればいいので都市1と3を結ぶ道路はいらないことがわかります。 つまり a + b = c　の場合の道路は入りません。
では a + b > cとなる道路はどうでしょうか？答えは必要です。 a + bでは他の都市を経由して行く場合の総距離が直接結んだ場合の距離より多くなってしまう場合には２都市間を結ぶ必要があります。

したがってまとめると
a + b < c となる場合が存在すれば -1
a + b = cとなる辺cは必要なし
a + b > cとなる辺cは必要あり

コード

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
using namespace std;

int d[303][303];
bool d_n[303][303];

int main(void){
  int n;
  cin >> n;

  long long ans = 0;
  for(int i=0; i<n; i++){
    for(int j=0; j<n; j++){
      cin >> d[i][j];
    }
  }
  for(int k=0; k<n; k++){
    for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){

        if(d[i][j] > d[i][k] + d[k][j]){
          cout << "-1" << endl;
          return 0;
        }

        if(d[i][j] == d[i][k] + d[k][j] && d[i][k] > 0 && d[k][j] > 0){
          d_n[i][j] = true;
        }

      }
    }
  }

  for(int i=0; i<n; i++){
    for(int j=0; j<=i; j++){

      if(d_n[i][j] == false){
        ans += d[i][j];
      }

    }
  }
  cout << ans << endl;
  return 0;
}