记录编号	597634	评测结果	AAAAAAAAAA
题目名称	[WC 2010模拟] 奶牛排队	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.052 s
提交时间	2024-12-08 17:26:38	内存使用	3.40 MiB

#include "bits/stdc++.h"

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    freopen("layout.in", "r", stdin);
    freopen("layout.out", "w", stdout);

    int n, m1, m2;
    std::cin >> n >> m1 >> m2;

    std::vector<std::vector<std::pair<int, int>>> adj(n + 1);
    for (int i = 1; i <= m1; ++ i) {
        int a, b, c;
        std::cin >> a >> b >> c;

        if (a > b) std::swap(a, b);
        adj[a].push_back({ b, c });
    }
    for (int i = 1; i <= m2; ++ i) {
        int a, b, c;
        std::cin >> a >> b >> c;

        if (a > b) std::swap(a, b);
        adj[b].push_back({ a, -c });
    }

    adj[0].push_back({ 1, 0 });
    adj[1].push_back({ 0, 0 });

    for (int i = 1; i <= n; ++ i) {
        adj[i].push_back({ i - 1, 0 });
        adj[i].push_back({ 0, 0 });
    }

    auto spfa = [&] () {
        std::vector<int> dist(n + 1, 1e9);
        dist[0] = 0;

        std::queue<std::pair<int, int>> q;
        std::vector<bool> st(n + 1);
        
        for (int i = 0; i <= n; ++ i) {
            q.push({ i, 0 }), st[i] = true;
        }

        while (q.size()) {
            auto [u, cnt] = q.front();
            q.pop(), st[u] = false;

            if (cnt >= n + 1) {
                return -1;
            }

            for (auto &[v, w] : adj[u]) {
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (!st[v]) {
                        q.push({ v, cnt + 1 }), st[v] = true;
                    }
                }
            }
        }

        if (dist[n] > 5e8) {
            return -2;
        } else {
            return dist[n];
        }
    };

    auto res = spfa();
    std::cout << res << '\n';

    return 0;
}