【題解】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";
}
分享本文 Share with friends