codeforces D. Design Tutorial: Inverse the Problem

对距离相同！

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>
#define N 2005
#define M 2000005
using namespace std; 

int mp[N][N];
int mpp[N][N];
int f[N];
int vis[N];
int n;

struct node{
    int v, dist;
    node(){}
    node(int v, int dist){
        this->v = v;
        this->dist = dist;
    }
};

vector<node>tmp[N];

struct edge{
    int x, y, d;
    edge(int x, int y, int d){
        this->x = x;
        this->y = y;
        this->d = d;
    }
    edge(){}
};

int cnt;
edge e[M];

bool cmp(edge a, edge b){
    return a.d < b.d;
}

int getFather(int x){
    return x == f[x] ? x : f[x] = getFather(f[x]);
}

bool _union(int x, int y){
    int fx = getFather(x), fy = getFather(y);
    if( fx != fy){
        f[fx] = fy;
        return true;
    }
    return false;
}

void dfs(int u, int cur, int dist){
    vis[u] = 1;
    int len = tmp[u].size();
    for(int i = 0; i<len; ++i){
        int v = tmp[u][i].v;
        if( !vis[v] ){
            mpp[cur][v] = mpp[v][cur] = dist+tmp[u][i].dist;
            dfs(v, cur, dist+tmp[u][i].dist);
        }
    }
}

int main(){
    scanf("%d", &n);
    bool flag = true;
    bool flag1 = false;    
    for(int i = 1; i <= n; ++i){
        f[i] = i;
        for(int j = 1; j <= n; ++j){
            scanf("%d", &mp[i][j]);
            if(j > i) e[cnt++] = edge(i, j, mp[i][j]);//将边存起来 
            if(i==j && mp[i][j] != 0) flag = false;//是否自身到自身有权值 
            if( i!=j && !mp[i][j]) flag1 = true;//是否都是全零 
        }
    }
    if(!flag1 && flag){
        sort(e, e+cnt, cmp);
        for(int i=0; i<cnt; ++i)
            if( _union(e[i].x, e[i].y) )
                tmp[e[i].x].push_back(node(e[i].y, e[i].d)), tmp[e[i].y].push_back(node(e[i].x, e[i].d));
       
        for(int i=1; flag && i<n; ++i){//求最小生成树中任意两个节点的距离 
            memset(vis, 0, sizeof(vis));
            dfs(i, i, 0);
            for(int j=i+1; flag && j<=n; ++j)
                if(!(mp[i][j] == mpp[i][j] && mp[i][j] == mp[j][i]))//如果最小生成树中的任意两点距离和给定的对应的两点之间的距离不相等 
                   flag = false;
        }
         
        if( flag ) printf("YES\n");
        else printf("NO\n");
    }
    else printf("NO\n");
    return 0;
}