题目链接

Layout POJ - 3169

思路

$$ 差分约束，注意条件a_i <= a_{i + 1}\\\\求最大值，即求最短路，x <= y + c\\\\求最小值，即求最长路，x >= y + c $$

时间复杂度

$$ O(NM) $$

代码

#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const long long INF = 0x3f3f3f3f3f3f3f3fLL;

class SPFA {
public:
    typedef long long T;

    // .first = v
    // .second.first = w;
    // .second.second = next;
    vector<int> head;
    typedef pair<int, pair<T, int> > P;
    vector<P> e;
    int tot;
    vector<T> dist;
    vector<int> cnt;
    vector<bool> inque;


    inline void init(int cnt_n, int cnt_m) {
        head.resize(cnt_n + 5);
        dist.resize(cnt_n + 5);
        cnt.resize(cnt_n + 5);
        inque.resize(cnt_n + 5);

        fill(head.begin(), head.end(), -1);
        e.resize(cnt_m * 2 + 10);
        tot = 0;
    }

    inline void add_edge(int u, int v, T w) {
        e[tot] = make_pair(v, make_pair(w, head[u]));
        head[u] = tot++;
    }

    inline void add_edges(int u, int v, T w) {
        add_edge(u, v, w);
        add_edge(v, u, w);
    }


    bool gao(int s) {
        fill(dist.begin(), dist.end(), INF);
        fill(cnt.begin(), cnt.end(), 0);
        fill(inque.begin(), inque.end(), false);
        queue<int> que;// queue or stack
        dist[s] = 0;
        que.push(s);
        cnt[s] = 1;
        inque[s] = true;

        while (!que.empty()) {
            int u = que.front();
            inque[u] = false;
            que.pop();
            for (int i = head[u]; ~i; i = e[i].second.second) {
                int v = e[i].first;
                T w = e[i].second.first;
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    if (!inque[v]) {
                        if (++cnt[v] > (int)head.size()) {
                           return false; 
                        }
                        inque[v] = true;
                        que.push(v);
                    }
                }
            }
        }

        return true;
    }

};

int main() {
    int n, a, b;
    scanf("%d%d%d", &n, &a, &b);// don't forget &
    SPFA spfa;
    spfa.init(n, a + b + n);
    for (int i = 1; i <= n - 1; i++) {
        spfa.add_edge(i + 1, i, 0);
    }
    for (int i = 1; i <= a; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);// don't forget &
        if (x > y) {
            swap(x, y);
        }
        spfa.add_edge(x, y, z);
    }

    for (int i = 1; i <= b; i++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);// don't forget &
        if (x > y) {
            swap(x, y);
        }
        spfa.add_edge(y, x, -z);
    }

    bool f = spfa.gao(1);
    if (f) {
        if (spfa.dist[n] == INF) {
            puts("-2");
        } else {
            printf("%lld", spfa.dist[n]);
        }
    } else {
        puts("-1");
    }

    return 0;
}