Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include<vector>
- #include <string>
- #include<algorithm>
- #include <iostream>
- #include <queue>
- #include<set>
- #include<unordered_set>
- #include<stack>
- #include<cmath>
- #include<math.h>
- #include<map>
- #include<unordered_map>
- #include<random>
- #include<chrono>
- #include <ctime>
- using namespace std;
- typedef long long ll;
- typedef pair<long long, long long> pll;
- #define mp make_pair
- #define fi(b, c) for(ll i = b; i <= c; i++)
- #define fj(b, c) for(ll j = b; j <= c; j++)
- #define fk(b, c) for(ll k = b; k <= c; k++)
- #define fq(b, c) for(ll q = b; q <= c; q++)
- #define fw(b, c) for(ll w = b; w <= c; w++)
- #define fim(b, c) for(ll i = b; i >= c; i--)
- #define fjm(b, c) for(ll j = b; j >= c; j--)
- #define fkm(b, c) for(l k = b; k >= c; k--)
- #define all(a) a.begin(), a.end()
- #define rall(a) a.rbegin(), a.rend()
- #define uniq(a) sort(all(a)); a.erase( unique( a.begin(), a.end() ), a.end() );
- // #define sz(a) (ll)(a.size())
- #define fs first
- #define sd second
- #define endl "\n"
- #define sz(x) (ll)(x.size())
- const ll inf = 1e9 + 123, llinf = 1e18 + 829, ura = 684395049517, mod = 998244353;
- void xru() {
- // 9 BOG 4EL
- // setlocale(LC_ALL, "rus");
- // freopen(".in", "r", stdin);
- // freopen(".out", "w", stdout);
- ios_base::sync_with_stdio(false);
- cin.tie(NULL);
- cout.tie(NULL);
- }
- void run() {
- cout << endl;
- system("pause");
- }
- /////////////////////////////////
- ll n, m;
- vector<vector<ll>>g, rg;
- vector<bool> used;
- vector<ll> dp, order;
- map<pll, ll> len;
- /////////////////////////////////
- void dfs(ll v){
- used[v] = true;
- for(ll to: g[v]){
- if(!used[to]) dfs(to);
- }
- order.push_back(v);
- }
- bool cond(ll v){
- used[v] = true;
- for(ll to: rg[v]){
- if(!used[to]){
- cout << "No";
- return 0;
- }
- }
- return 1;
- }
- int main() {
- cin >> n >> m;
- g.resize(n);
- rg.resize(n);
- used.resize(n, false);
- dp.resize(n, -1);
- fi(0, m-1){
- ll l, r, d;
- cin >> l >> r >> d;
- // if(l == 3 && r == 1) cout << "BLIN";
- g[l-1].push_back(r-1);
- rg[r-1].push_back(l-1);
- len[{l-1, r-1}] = d;
- }
- // fi(0, n-1){
- // cout << i+1 << ": ";
- // for(ll to: g[i]) cout << to+1 << " ";
- // cout << endl;
- // }
- fi(0, n-1){
- if(!used[i]) dfs(i);
- }
- reverse(all(order));
- fi(0, n-1) used[i] = false;
- fi(0, n-1){
- if(!used[order[i]]){
- if(!cond(order[i])) return 0;
- }
- }
- bool first = true;
- // cout << order.size() << endl;
- for(ll now: order){
- // cout << now + 1 << "-";
- if(first) {
- dp[now] = 0;
- // cout << dp[now] << " ";
- first = false;
- continue;
- }
- for(ll from: rg[now]){
- if(dp[now] == -1){
- dp[now] = dp[from] + len[{from, now}];
- } else if(dp[now] != dp[from] + len[{from, now}]){
- cout << "No";
- return 0;
- }
- }
- if(rg[now].empty()) dp[now] = 0;
- // cout << dp[now] << "; ";
- }
- cout << "Yes";
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement