Submission #50670075

---

Source Code Expand

import std;

void main () {
    int N = readln.chomp.to!int;
    auto A = new int[][](N, 0);
    foreach (i; 0..N) A[i] = readln.split.to!(int[]);

    solve(N, A);
}

void solve (int N, int[][] A) {
    // worst Θ(N^3)解法

    Tuple!(int, int, int)[] edges;

    foreach (i; 0..N) {
        foreach (j; i+1..N) {
            edges ~= tuple(i, j, A[i][j]);
        }
    }

    edges.sort!"a[2] < b[2]";

    long ans = 0;

    auto dist = new long[][](N, N);
    foreach (d; dist) d[] = long.max;
    foreach (i; 0..N) dist[i][i] = 0;
    foreach (e; edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];

    foreach (k; 0..N) {
        foreach (i; 0..N) foreach (j; 0..N) {
            if (dist[i][k] == long.max || dist[k][j] == long.max) continue;
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }

    bool ok = true;

    foreach (e; edges) {
        long d = long.max;
        foreach (i; 0..N) {
            if (i == e[0] || i == e[1]) continue;
            d = min(d, dist[e[0]][i] + dist[i][e[1]]);
        }

        if (d == e[2]) continue;
        if (d < e[2]) ok = false;

        if (e[2] < d) {
            ans += e[2];
        }
    }

    if (ok) {
        writeln(ans);
    }
    else {
        writeln(-1);
    }
}

Submission Info

Compile Error

/home/runner/.dub/packages/mir-algorithm/3.20.4/mir-algorithm/source/mir/serde.d(52,9): Deprecation: alias this for classes/interfaces is deprecated

Judge Result