Submission #50664969

---

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) {
    // 非負の辺しかないので、Aの最小の値に関しては確定できる。
    // それ以外にも、重みの昇順に見ていくことを考えると、
    // 1. 重み分の辺をはる
    // 2. すでに制約が満たされている
    // のどちらかしかありえない。なぜなら、重みより小さい辺を新しくはると別の場所で制約違反が必ず起きるし、より大きな辺をはるとどうやっても達成できないから。
    // さらに、追加していく辺が重み昇順であることを考えると、タイプ1の時はチェックすらしなくてよい。

    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;

    bool ok = true;

    foreach (e; edges) {
        if (dist[e[0]][e[1]] == e[2]) continue;
        if (dist[e[0]][e[1]] < e[2]) ok = false;

        if (e[2] < dist[e[0]][e[1]]) {
            ans += e[2];

            // floyd-warshallっぽく更新
            // 辺をセット
            dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2];

            foreach (i; 0..N) foreach (j; 0..N) {
                if (dist[i][e[0]] < long.max && dist[e[1]][j] < long.max) {
                    dist[i][j] = dist[j][i] = min(dist[i][j], dist[i][e[0]] + dist[e[0]][e[1]] + dist[e[1]][j]);
                }
            }
        }
    }

    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