Language: C++

#include <bits/stdc++.h>

#define TYPE(c)   remove_reference_t<decltype(c)>
#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)
#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)
#define ALL(c)    c.begin(), c.end()
#define SORT(c)   sort(ALL(c))
#define RSORT(c)  sort(ALL(c), greater<TYPE(c)::value_type>())
#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())

using namespace std;
using ll = long long;

constexpr int MOD  = (int)1e9 + 7;
constexpr int INF  = (int)1e9 + 1;
constexpr ll  LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b)
{ if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b)
{ if(b < a) { a = b; return true; } else { return false; } }
template<typename S, typename T> ostream& operator<<(ostream &os, const pair<S, T>& p)
{ return os << "(" << p.first << "," << p.second << ")"; }
template<typename T> auto operator<<(ostream& os, const T& t)
    -> typename conditional<true, ostream&, decltype(*t.begin())>::type
{ os << "["; FOR(v, t) { if(v != t.begin()) os << ","; os << *v; } os << "]"; return os; }

class Graph {
    using ll = long long;
public:
    enum class Type { Directed, Undirected };
    struct Edge {
        ll   cost;
        bool validity;
        explicit Edge(const ll& _cost) :
            cost(_cost), validity(true) { }
        friend std::ostream& operator <<(std::ostream& os, const std::shared_ptr<Edge>& e) {
            os << "cost : " << e->cost << ", " << "validity : " << e->validity;
            return os;
        }
    };
    struct Vertex {
        ll cost;
        explicit Vertex(const ll& _cost) : cost(_cost) { }
        friend std::ostream& operator <<(std::ostream& os, const Vertex& v) {
            os << "cost : " << v.cost;
            return os;
        }
    };
    const Type edge_type;
    std::vector<Vertex> vertices;
    std::vector<std::map<ll, std::shared_ptr<Edge>>> edges;
    Graph(const ll& nof_vertex, const Type& edge_type, const ll& vertices_initial_cost = (ll)1e9 + 1) :
        edge_type(edge_type), vertices(nof_vertex, Vertex(vertices_initial_cost)), edges(nof_vertex) { }
    void setCostToAllVertices(const ll& cost) {
        std::fill(vertices.begin(), vertices.end(), cost);
    };
    void addEdge(const ll& src, const ll& dst, const ll& cost = 1) {
        auto edge = std::make_shared<Edge>(cost);
        edges[src].emplace(dst, edge);
        if(edge_type == Type::Undirected) edges[dst].emplace(src, edge);
    }
    friend std::ostream& operator <<(std::ostream& os, const Graph& g) {
        os << std::endl
           << "--- Vertex Information ---" << std::endl;
        for(size_t i = 0; i < g.vertices.size(); i++)
            os << "[[" << i << "] " << g.vertices[i] << "]" << std::endl;
        os << "---- Edge Information ----" << std::endl;
        for(size_t i = 0; i < g.vertices.size(); i++)
            for(const auto& e : g.edges[i])
                os << "[" << i << " -> " << e.first  << "] " << "[" << e.second << "]" << std::endl;
        os << "--------------------------";
        return os;
    }
};

/**
 *  全頂点間の最短距離を求める(Warshall-Floyd法)
 *  NOTE: 計算量O(|V|^3)
 *  @Return: array[i][j] :: 頂点iから頂点jまでの最短距離
 */
// 使用例(グラフの直径)
// auto table    = warshall_floyd(g);
// auto diameter = 0;
// REP(i, g.vertices.size()) {
//     REP(j, g.vertices.size()) {
//         if(j <= i) continue;
//         chmax(diameter, table[j][i]);
//     }
// }
std::vector<std::vector<ll>> warshall_floyd(const Graph& g,
                                            const ll& inf_val = (ll)1e18 + 1) {
    std::vector<std::vector<ll>> dp(g.vertices.size(), std::vector<ll>(g.vertices.size(), inf_val));
    for(size_t i = 0; i < g.edges.size(); i++)
        for(const auto& e : g.edges[i])
            dp[i][e.first] = e.second->cost;
    for(size_t i = 0; i < g.vertices.size(); i++)
        for(size_t j = 0; j < g.vertices.size(); j++)
            for(size_t k = 0; k < g.vertices.size(); k++)
                dp[j][k] = std::min(dp[j][k], dp[j][i] + dp[i][k]);
    return dp;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N;
    std::cin >> N;

    Graph g(N, Graph::Type::Undirected);

    vector<vector<ll>> A(N, vector<ll>(N, 0));
    REP(i, N) {
        REP(j, N) {
            std::cin >> A[i][j];
            if(i <= j) continue;
            g.addEdge(i, j, A[i][j]);
        }
    }

    auto dp = warshall_floyd(g);

    ll ans = 0;
    [&]() {
        REP(i, N) {
            REP(j, N) {
                if(i <= j) continue;
                if(dp[i][j] < A[i][j]) {
                    ans = -1;
                    return;
                }
                bool direct = true;
                REP(k, N) {
                    if(k == i || k == j) continue;
                    if(dp[i][j] == A[i][k] + A[k][j]) {
                        direct = false;
                        break;
                    }
                }
                if(direct) ans += dp[i][j];
            }
        }
    }();

    std::cout << ans << std::endl;

    return 0;
}


Compiler output:
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h: In instantiation of 'typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = Graph::Vertex*; _Tp = long long int; typename __gnu_cxx::__enable_if<__is_scalar<_Tp>::__value, void>::__type = void]':
/usr/include/c++/14/bits/stl_algobase.h:981:21:   required from 'void std::__fill_a1(__gnu_cxx::__normal_iterator<_Iterator, _Container>, __gnu_cxx::__normal_iterator<_Iterator, _Container>, const _Tp&) [with _Ite = Graph::Vertex*; _Cont = vector<Graph::Vertex>; _Tp = long long int]'
  981 |     { std::__fill_a1(__first.base(), __last.base(), __value); }
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:998:21:   required from 'void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = __gnu_cxx::__normal_iterator<Graph::Vertex*, vector<Graph::Vertex> >; _Tp = long long int]'
  998 |     { std::__fill_a1(__first, __last, __value); }
      |       ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:1029:20:   required from 'void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = __gnu_cxx::__normal_iterator<Graph::Vertex*, vector<Graph::Vertex> >; _Tp = long long int]'
 1029 |       std::__fill_a(__first, __last, __value);
      |       ~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:55:18:   required from here
   55 |         std::fill(vertices.begin(), vertices.end(), cost);
      |         ~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:952:18: error: no match for 'operator=' (operand types are 'Graph::Vertex' and 'const long long int')
  952 |         *__first = __tmp;
      |         ~~~~~~~~~^~~~~~~
a.cc:41:12: note: candidate: 'constexpr Graph::Vertex& Graph::Vertex::operator=(const Graph::Vertex&)'
   41 |     struct Vertex {
      |            ^~~~~~
a.cc:41:12: note:   no known conversion for argument 1 from 'const long long int' to 'const Graph::Vertex&'
a.cc:41:12: note: candidate: 'constexpr Graph::Vertex& Graph::Vertex::operator=(Graph::Vertex&&)'
a.cc:41:12: note:   no known conversion for argument 1 from 'const long long int' to 'Graph::Vertex&&'