CFR 270 D. Design Tutorial: Inverse the Problem ( MST )

Problem - D - Codeforces
First we will have to take away apparently wrong cases, where
dis[ i ][ i ] != 0 or dis[ i ][ j ] == 0 for i != j, or if dis[ i ][ j ] != dis[ j ][ i ].
We will find that we are willing to make a tree, so the shortest path between each pair of vertices must be unique. That means, if we take the minimum spanning tree from the given adjacency matrix, it should be able to describe exactly the same distance matrix, otherwise it will imply that the matrix cannot be formed by a tree. So we will only have to get the mst O( n ^ 2 lg n ), then get the distance matrix from it with O( n ^ 2 ) by DFS or BFS.
And be careful with the case where there is only one vertex.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e3 + 3;
const int MAXD = 1e9 + 9;
typedef pair< int, int > pii;

int n;
int d[ MAXN ][ MAXN ];

struct Edge{
    int u, v, w;
    Edge( int _u = -1, int _v = -1, int _w = -1 ):
        u(_u), v(_v), w(_w){}
    bool operator < ( const Edge &oth ) const{
        return w < oth.w;
    }
};

int es_cnt;
Edge es[ MAXN * MAXN ];
vector< Edge > G[ MAXN ];

struct UnionFind{
    int fa[ MAXN ];
    void init( int _n ){
        for( int i = 0; i < _n; ++i )
            fa[ i ] = i;
    }
    int find( int x ){ return fa[ x ] == x ? x : fa[ x ] = find( fa[ x ] ); }
    bool unite( int x, int y ){
        int a = find( x );
        int b = find( y );
        if( a == b ) return false;
        fa[ a ] = b; return true;
    }
} uf;

struct MST{
    int chose_cnt;
    vector< Edge > chose[ MAXN ];
    int dis[ MAXN ][ MAXN ];
    void solve(){
        uf.init( n );
        sort( es, es + es_cnt );
        for( int i = 0; i < es_cnt; ++i ){
            int u = es[ i ].u;
            int v = es[ i ].v;
            int w = es[ i ].w;
            if( uf.unite( u, v ) ){
                chose[ u ].push_back( Edge( u, v, w ) );
                chose[ v ].push_back( Edge( v, u, w ) );
                if( ++chose_cnt == n - 1 )
                    return;
            }
        }
        assert( false );
    }
    void dfs( int u, int fa, int w, vector< int > &vis ){
        for( int v : vis )
            dis[ u ][ v ] = dis[ v ][ u ] = dis[ fa ][ v ] + w;
        vis.push_back( u );
        for( Edge &e : chose[ u ] ){
            if( e.v == fa ) continue;
            dfs( e.v, u, e.w, vis );
        }
    }
    void computeDis(){
        vector< int > vis;
        dfs( 0, -1, 0, vis );
    }
} mst;

void solve(){
    if( n == 1 ) return (void)( puts( d[ 0 ][ 0 ] ? "NO" : "YES" ) );
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ){
            if( i == j && d[ i ][ j ] )
                return (void)puts("NO");
            if( i != j && d[ i ][ j ] == 0 )
                return (void)puts("NO");
        }
    for( int i = 0; i < n; ++i )
        for( int j = i + 1; j < n; ++j )
            if( d[ i ][ j ] != d[ j ][ i ] )
                return (void)puts("NO");
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j ) if( i != j ){
            Edge e = Edge( i, j, d[ i ][ j ] );
            es[ es_cnt++ ] = e;
            G[ i ].push_back( e );
        }
    mst.solve();
    mst.computeDis();
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j )
            if( d[ i ][ j ] != mst.dis[ i ][ j ] )
                return (void)puts("NO");
    puts("YES");
}

int main(){
    scanf("%d", &n);
    for( int i = 0; i < n; ++i )
        for( int j = 0; j < n; ++j )
            scanf("%d", &d[ i ][ j ]);
    solve();
    return 0;
}