比赛 4043级NOIP2022欢乐赛2nd 评测结果 AWAAAWAAAA
题目名称 奶牛排队 最终得分 80
用户昵称 lihaoze 运行时间 0.724 s
代码语言 C++ 内存使用 0.60 MiB
提交时间 2022-10-31 19:09:57
显示代码纯文本
#include "bits/stdc++.h"

const int N = 10010;
int n, l, d, dist[N], st[N], cnt[N];
int e[N], ne[N], h[N], w[N], idx;

void add(int a, int b, int x) {
    e[idx] = b, ne[idx] = h[a], w[idx] = x, h[a] = idx ++;
}

void spfa() {
    memset(dist, 0x3f, sizeof dist);
    std::queue<int> q;
    q.push(1), dist[1] = 0, st[1] = true, cnt[1] = 1;
    while (q.size()) {
        int u = q.front(); q.pop();
        st[u] = false;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (dist[v] > dist[u] + w[i]) {
                dist[v] = dist[u] + w[i];
                if (!st[v]) {
                    ++ cnt[v];
                    q.push(v), st[v] = true;
                }
            }
        }
    }
}

int main() {
    freopen("layout.in", "r", stdin); 
    freopen("layout.out", "w", stdout);
    memset(h, -1, sizeof h);
    std::cin >> n >> l >> d;
    for (int i = 1; i <= l; ++ i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        add(x, y, w); 
    }
    for (int i = 1; i <= d; ++ i) {
        int x, y, w;
        std::cin >> x >> y >> w;
        add(y, x, -w);
    }
    spfa();
    for (int i = 1; i <= n; ++ i) {
        if (cnt[i] > n) {
            return std::cout << -2 << '\n', 0;
        }
    }
    if (dist[n] == 0x3f3f3f3f) {
        std::cout << -1 << '\n';
    } else {
        std::cout << dist[n] << '\n';
    }
    return 0;
}

// d_a - d_b >= l => d_a >= l + d_b
// d_a - d_b <= l => d_b >= -l + d_a