lessons/参考实现/05-最短路与类最短路/POJ-3169.cpp

#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
struct Edge { int from, to; long long weight; };

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, like_count, dislike_count;
    cin >> n >> like_count >> dislike_count;
    vector<Edge> edges;
    for (int i = 0; i + 1 < n; ++i) edges.push_back({i + 1, i, 0});
    while (like_count--) {
        int a, b; long long d; cin >> a >> b >> d; --a; --b;
        edges.push_back({a, b, d});
    }
    while (dislike_count--) {
        int a, b; long long d; cin >> a >> b >> d; --a; --b;
        edges.push_back({b, a, -d});
    }

    vector<long long> all(n, 0);
    for (int iteration = 0; iteration < n; ++iteration) {
        bool changed = false;
        for (Edge e : edges) if (all[e.to] > all[e.from] + e.weight) {
            all[e.to] = all[e.from] + e.weight; changed = true;
        }
        if (!changed) break;
        if (iteration == n - 1) { cout << "-1\n"; return 0; }
    }

    const long long inf = numeric_limits<long long>::max() / 4;
    vector<long long> dist(n, inf); dist[0] = 0;
    for (int iteration = 0; iteration + 1 < n; ++iteration) {
        bool changed = false;
        for (Edge e : edges) if (dist[e.from] != inf &&
                dist[e.to] > dist[e.from] + e.weight) {
            dist[e.to] = dist[e.from] + e.weight; changed = true;
        }
        if (!changed) break;
    }
    cout << (dist[n - 1] == inf ? -2 : dist[n - 1]) << '\n';
}