Submission #3452089

---

Source Code Expand

#include<bits/stdc++.h>
#define N 200010
using namespace std;
struct edge{int ne,to,w;}e[N];
int x,y,w,n,m,es,head[N],vis[N],cal[N],ys=1,mx,mn,ans;
inline int read(){
	int x=0,sgn=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar())if(ch=='-')sgn=-1;
	for(;isdigit(ch);ch=getchar())x=x*10+(ch^48);
return sgn*x;
}
inline void add(int x,int y,int w){
	e[++es]=(edge){head[x],y,w};
	head[x]=es;
}
inline void dfs(int x){
	vis[x]=1;mx=max(mx,cal[x]),mn=min(mn,cal[x]);
	for(int i=head[x];i;i=e[i].ne){
		int v=e[i].to;
		if(ys==0) return;
		if(vis[v]) {if(cal[v]!=cal[x]+e[i].w) {ys=0;return;}}
		else{
			cal[v]=cal[x]+e[i].w;
			dfs(v);
		}
	}
}
int main(){
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		x=read(),y=read(),w=read();
		if(x==y) continue;
		add(x,y,w),add(y,x,-w);
	}
	for(int i=1;i<=n;i++){
		mx=-1e9,mn=1e9;
		if(!vis[i]) dfs(i);
		if(ys==0) {printf("No");return 0;}
		ans=max(ans,mx-mn);
	}
	printf("Yes");
return 0;
}

Submission Info

Judge Result