30 lines
1.1 KiB
C++
30 lines
1.1 KiB
C++
// P1993 小K的农场。上界边 x[v] <= x[u]+w，全图判负环。
|
|
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
using ll = long long;
|
|
int main() {
|
|
ios::sync_with_stdio(false); cin.tie(nullptr);
|
|
int n, m; if (!(cin >> n >> m)) return 0;
|
|
vector<vector<pair<int,ll>>> g(n + 1);
|
|
auto add = [&](int u, int v, ll w) { g[u].push_back({v,w}); };
|
|
for (int i = 0, type, a, b; i < m; ++i) {
|
|
cin >> type >> a >> b; ll c;
|
|
if (type == 1) { cin >> c; add(a,b,-c); }
|
|
else if (type == 2) { cin >> c; add(b,a,c); }
|
|
else { add(a,b,0); add(b,a,0); }
|
|
}
|
|
vector<ll> dist(n + 1, 0);
|
|
vector<int> len(n + 1, 0);
|
|
vector<bool> inq(n + 1, true);
|
|
queue<int> q; for (int i = 1; i <= n; ++i) q.push(i);
|
|
while (!q.empty()) {
|
|
int u = q.front(); q.pop(); inq[u] = false;
|
|
for (auto [v,w] : g[u]) if (dist[v] > dist[u] + w) {
|
|
dist[v] = dist[u] + w; len[v] = len[u] + 1;
|
|
if (len[v] >= n) { cout << "No\n"; return 0; }
|
|
if (!inq[v]) { q.push(v); inq[v] = true; }
|
|
}
|
|
}
|
|
cout << "Yes\n";
|
|
}
|