【題解】Luogu P1993 小 K 的农场

【題目敘述】https://www.luogu.com.cn/problem/P1993
【解題想法】差分約束

```#include <iostream>
#include <vector>
#include <cstring>
#include <stack>
#include <queue>
using namespace std;

int n, m;
vector <pair<int, int> > v[5005];

int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
int t, a, b, c;
for (int i = 0; i < m; i++){
cin >> t;
if (t == 1){
cin >> a >> b >> c;
v[a].push_back({b, -c});
}
else if (t == 2){
cin >> a >> b >> c;
v[b].push_back({a, c});
}
else{
cin >> a >> b;
v[a].push_back({b, 0});
v[b].push_back({a, 0});
}
}
for (int i = 1; i <= n; i++){
v[0].push_back({i, 0});
}
queue <int> q;
int in[5005] = {}, cnt[5005] = {}, dis[5005];
memset(dis, 0x3F, sizeof(dis));
q.push(0);
dis[0] = 0;
bool flag = true;
while (!q.empty()){
int x = q.front();
q.pop();
in[x] = 0;
for (auto &i:v[x]){
if (dis[x]+i.second < dis[i.first]){
dis[i.first] = dis[x]+i.second;
cnt[i.first] = cnt[x]+1;
if (cnt[i.first] > n){
flag = false;
break;
}
if (!in[i.first]){
q.push(i.first);
in[i.first] = 1;
}
}
}
if (!flag) break;
}
if (!flag) cout << "No\n";
else cout << "Yes\n";
}
```