蒜头君的银行卡

蒜头君的银行卡"/>

蒜头君的银行卡

虽然蒜头君并没有多少钱，但是蒜头君办了很多张银行卡，共有 n 张，以至于他自己都忘记了每张银行卡里有多少钱了。
他只记得一些含糊的信息，这些信息主要以下列三种形式描述：
银行卡 a 比银行卡 b 至少多 c 元。
银行卡 a 比银行卡 b 至多多 c 元。
银行卡 a 和银行卡 c 里的存款一样多。
但是由于蒜头君的记忆有些差，他想知道是否存在一种情况，使得银行卡的存款情况和他记忆中的所有信息吻合。

输入格式
第一行输入两个整数 n 和 m，分别表示银行卡数目和蒜头君记忆中的信息的数目。(1≤n,m≤10000)
接下来 m 行：
如果每行第一个数是 1，接下来有三个整数 a,b,c，表示银行卡 a 比银行卡 b 至少多 c 元。
如果每行第一个数是 2，接下来有三个整数 a,b,c，表示银行卡 a 比银行卡 b 至多多 c 元。
如果每行第一个数是 3，接下来有两个整数 a,b，表示银行卡 a 和 b 里的存款一样多。(1≤n,m,a,b,c≤10000)

输出格式
如果存在某种情况与蒜头君的记忆吻合，输出Yes，否则输出No。

样例输入
3 3
3 1 2
1 1 3 1
2 2 3 2
样例输出
Yes

#include <bits/stdc++.h>using namespace std;
const int N = 1e4 + 10;
int head[N], ver[N * 2], Next[N * 2], tot, edge[N * 2];
int cnt[N], d[N];
bool v[N];
int n, m;void add(int x, int y, int z) {ver[++tot] = y;edge[tot] = z;Next[tot] = head[x];head[x] = tot;
}void read() {cin >> n >> m;for (int i = 1; i <= m; i++) {int a, b, c, t;scanf("%d", &t);if (t == 1) {scanf("%d%d%d", &a, &b, &c);add(b, a, c);}if (t == 2) {scanf("%d%d%d", &a, &b, &c);add(a, b, -c);}if (t == 3) {scanf("%d%d", &a, &b);add(a, b, 0);add(b, a, 0);}}
}bool spfa() {for (int i = 2; i <= n; i++)d[i] = -1e9;queue<int> q;q.push(1);v[1] = true;while (!q.empty()) {int x = q.front();q.pop();v[x] = false;for (int i = head[x]; i; i = Next[i]) {int y = ver[i], z = edge[i];if (d[y] < d[x] + z) {d[y] = d[x] + z;cnt[y] = cnt[x] + 1;if (cnt[y] >= n)return false;if (!v[y]) {q.push(y);v[y] = true;}}}}return true;
}int main() {read();if (spfa())cout << "Yes";elsecout << "No";return 0;
}