排队布局

排队布局

实现

#include <iostream>
#include <cstring>
#include <queue>
#define inf 0x3f3f3f3f
using namespace std;

const int N = 1010, M = 21010;
struct edge {
    int to, next, w;
};
edge e[M];
int idx, head[N];
int n, m1, m2;
int dis[N], cnt[N];
bool mark[N];

void add_edge (int u, int v, int w) {
    e[idx].w = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx ++;
}
bool spfa (int k) { // 1 ~ k
    memset(mark, 0, sizeof(mark));
    memset(cnt, 0, sizeof(cnt));
    memset(dis, 0x3f, sizeof(dis));

    queue<int> q;
    for (int i = 1; i <= k; ++ i) {
        dis[i] = 0;
        q.push(i);
        mark[i] = true;
    }
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        mark[cur] = false;
        for (int i = head[cur]; i != -1; i = e[i].next) {
            int to = e[i].to, w = e[i].w;
            if (dis[cur] + w < dis[to]) {
                dis[to] = dis[cur] + w;
                cnt[to] = cnt[cur] + 1;
                if (cnt[to] >= n) return true;
                if (mark[to] == false) {
                    q.push(to);
                    mark[to] = true;
                }
            }
        }
    }
    return false;
}

int main () {
    memset(head, -1, sizeof(head));
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= n; ++ i) add_edge(i + 1, i, 0);
    for (int i = 1, u, v, w; i <= m1; ++ i) {
        cin >> u >> v >> w;
        if (u > v) swap(u, v);
        add_edge(u, v, w);
    }
    for (int i = 1, u, v, w; i <= m2; ++ i) {
        cin >> u >> v >> w;
        if (u > v) swap(u, v);
        add_edge(v, u, -w);
    }

    if (spfa(n) == true) { // 有负环
        cout << -1 << endl;
    } else {
        spfa(1);
        cout << (dis[n] == inf ? -2 : dis[n]) << endl;
    }
    return 0;
}