Submission #3813035

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

#define inf (ll)1e12
struct edge{ll to,cost;};
edge e;
ll a[10001];
bool used[10001];
bool flag;

void dfs(vector<edge> G[], int node){
    for(auto x : G[node]){
        if(a[x.to]!=inf && a[x.to]!=a[node]+x.cost)flag=1;
        else a[x.to]=a[node]+x.cost;
        if(used[x.to]==0){
            used[x.to]=1;
            dfs(G,x.to);
        }
    }
}

int main(void){
    int n,m;
    cin>>n>>m;
    int l,r,d;
    vector<edge> G[n];
    
    for(int i=0;i<m;i++){
        cin>>l>>r>>d;
        l--;r--;
        e.to=r; e.cost=d;
        G[l].push_back(e);
        e.to=l; e.cost=-1*d;
        G[r].push_back(e);
    }
    for(int i=0;i<n;i++)a[i]=inf;
    for(int i=0;i<n;i++){
        if(a[i]==inf){a[i]=0;dfs(G,i);}
        else dfs(G,i);
    }
    cout<<(flag ? "NO" : "YES")<<endl;
}

Submission Info

Judge Result