Submission #1694364

---

Source Code Expand

import std.algorithm;
import std.array;
import std.ascii;
import std.container;
import std.conv;
import std.format;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

alias P = Tuple!(int, "from", int, "to");
alias Q = Tuple!(int, "to", long, "cost");
long[][] a;
alias RBT = RedBlackTree!(P, (p, q) => a[p.from][p.to] < a[q.from][q.to], true);

void main()
{
  int n = readln.chomp.to!int;
  a = new long[][](n);
  foreach (i; 0 .. n)
  {
    a[i] = readln.chomp.split.map!(to!long).array;
  }
  RBT queue = new RBT();
  foreach (i; 0 .. n)
  {
    foreach (j; i + 1 .. n)
    {
      queue.insert(P(i, j));
    }
  }
  Q[][] adj = new Q[][](n);
  long[][] dist = new long[][](n, n);
  foreach (i, ref arr; dist)
  {
    arr[] = 1L << 60;
    arr[i] = 0;
  }
  bool ng = false;
  while (queue.length)
  { // O(n^2 log n)
    P node = queue.front;
    queue.removeFront;
    foreach (i; 0 .. n)
    {
      if (dist[i][node.to] > dist[i][node.from] + dist[node.from][node.to])
      {
        dist[i][node.to] = dist[node.to][i] = dist[i][node.from] + dist[node.from][node.to];
      }
      if (dist[node.from][i] > dist[node.from][node.to] + dist[node.to][i])
      {
        dist[node.from][i] = dist[i][node.from] = dist[node.from][node.to] + dist[node.to][i];
      }
    }
    long atom = dist[node.from][node.to];
    long vs = a[node.from][node.to];
    if (atom < vs)
    {
      ng = true;
      break;
    }
    if (atom == vs)
    {
      continue;
    }
    // link
    // stderr.writeln(node.from, " ", node.to, " : ", vs);
    adj[node.from] ~= Q(node.to, vs);
    adj[node.to] ~= Q(node.from, vs);
    dist[node.from][node.to] = vs;
    dist[node.to][node.from] = vs;
    foreach (i; 0 .. n)
    {
      if (dist[i][node.to] > dist[i][node.from] + dist[node.from][node.to])
      {
        dist[i][node.to] = dist[node.to][i] = dist[i][node.from] + dist[node.from][node.to];
      }
      if (dist[node.from][i] > dist[node.from][node.to] + dist[node.to][i])
      {
        dist[node.from][i] = dist[i][node.from] = dist[node.from][node.to] + dist[node.to][i];
      }
    }
    /+
    foreach (i; 0..n) {
      foreach (j; 0..n) {
        if (j) stderr.write = " ";
        stderr.write = dist[i][j] == 1L << 60 ? "*" : dist[i][j].to!string;
      }
      stderr.writeln;
    }
    stderr.writeln;
    +/
  }
  /+
  foreach (i; 0..n) {
    foreach (j; 0..n) {
      ng |= a[i][j] != dist[i][j];
    }
  }
  +/
  if (ng)
  {
    writeln = -1;
    return;
  }

  long sum = 0;
  foreach (arr; adj)
  {
    foreach (q; arr)
    {
      sum += q.cost;
    }
  }
  sum /= 2;
  
  sum.writeln;
}

Submission Info

Judge Result