Submission #2034615

---

Source Code Expand

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
/////////////////// TYPES & MACROS ///////////////////////////////
#define INFLL 0x3fffffffffffffffLL
#define INF 0x3fffffff
#define mp make_pair
#define eb emplace_back
#define pb push_back
#define all(x) x.begin(),x.end()
#define exist(s,e) (s.find(e)!=s.end())
#define ff first
#define ss second
#define EPS 1e7
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef tree<int,null_type,less<int>,rb_tree_tag,
tree_order_statistics_node_update> indexed_set;
const ll MOD=1e9+7;
/////////////////// DEBUG MODE ///////////////////////////////////
#define D(x) cerr<<"DEBUG: "<<#x<<" is: "<<x<<'\n'
#define error(args...) {string _s=#args; replace(all(_s),',',' ');\
stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args);}
void err(istream_iterator<string>) { cout<<endl;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
	cerr << *it << " = " << a << endl;
	err(++it, args...);
}
/////////////////// GLOBAL VARIABLES /////////////////////////////
vector<vector<int>> adj; vector<int> vis; vector<int> color;
/////////////////// FUNCTIONS ////////////////////////////////////
template<class T>
T maxx(T a, T b) {return a>b?a:b;}
template<typename T, typename... Args>
T maxx(T a, T b, Args... args){return maxx(a>b?a:b, args...);}
ll mexp(ll x, ll n, ull m){
  ll res=1;  while(n){if(n&1) res=(res*x)%m;n>>=1; x=((x%m)*(x%m))%m;}
  return res;
}
template<class T>
T minn(T a, T b) {return a<b?a:b;}
template<typename T, typename... Args>
T minn(T a, T b, Args... args){return minn(a>b?a:b, args...);}
bool ispow2(ll x){ return x && (!(x&(x-1))); }
ld pow(ld a, int n) {
  if(n == 0) return 1;if(n == 1) return a;
  double t = pow(a, n/2);return t * t * pow(a, n%2);
}

bool DFS(int u){
	vis[u]=1;
	for(auto v: adj[u]){
		if(!vis[v]) {if(!DFS(v)) return false;}
		else if(vis[v]==1) return false;
	}
	vis[u]=2;
	return true;
}
bool cycle(){
	int n=adj.size();
	vis.assign(n,0);
	for(int i=0;i<n;++i) if(!vis[i] && !DFS(i)) return true;
	return false;
}
vector<int> ts;
void toposort(int u){
	vis[u]=1;
	for(auto v: adj[u]) if(!vis[v]) toposort(v);
	ts.eb(u);
}
/////////////////// MAIN STARTS //////////////////////////////////
int main(){
  ios::sync_with_stdio(0);  cin.tie(0);   cout<<fixed; cerr<<fixed;
  cout<<setprecision(10); cerr<<setprecision(3);
  #ifdef DEBUG
  freopen("ip.txt","r",stdin); //freopen("op.txt","w",stdout);
  clock_t tStart = clock();
  #endif

	int n,m; cin>>n>>m; adj.resize(n); vis.assign(n,0);
	map<pii,int> wt;
	for(int i=0;i<m;++i){
		int u,v,x; cin>>u>>v>>x; --u,--v;
		adj[u].eb(v); wt[{u,v}]=x;
	}
	if(cycle()) {cout<<"No\n"; return 0;}
	else{
		fill(all(vis),0);
		vector<int> d(n,INF),indeg(n,0);
		for(int i=0;i<n;++i){
			for(auto v: adj[i]) indeg[v]++;
		}
		queue<int> q;
		for(int i=0;i<n;++i) if(indeg[i]==0) q.push(i),d[i]=0;
		while(!q.empty()){
			int u=q.front(); q.pop();
			for(auto v:adj[u]){
				if(vis[v]==0){ q.push(v); vis[v]=1; }
				if(d[v]==INF) d[v]=d[u]+wt[{u,v}];
				else if(d[v] != d[u]+wt[{u,v}]) {cout<<"No\n"; return 0;}
			}
		}
	}
	cout<<"Yes\n";




	#ifdef DEBUG
	cerr<<"\nExecution time: "<<(((double)clock() - tStart)/CLOCKS_PER_SEC)*1000<<"ms.\n";
	#endif
  return 0;
}

Submission Info

Judge Result