差分约束37pts求条
查看原帖
差分约束37pts求条
1140231
ChangeYuAN楼主2024/10/2 21:53
#include <bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f, N = 1e6 + 5, M = 2e6 + 5;
int n, m1, m2, m;
int head[N], cnt;

struct edge {
	int to, next, w;
} e[M];

void init() {
	for (int i = 0; i < N; ++i)
		head[i] = -1;
	for (int i = 0; i < M; ++i)
		e[i].next = -1;
	cnt = 0;
}

void addedge(int u, int v, int w) {
	e[cnt].to = v, e[cnt].w = w, e[cnt].next = head[u];
	head[u] = cnt++;
}

int dis[N], Neg[N];
bool inq[N];

int spfa(int s) {
	memset(Neg, 0, sizeof(Neg));
	Neg[s] = 1;
	for (int i = 1; i <= n; i++) {
		dis[i] = inf, inq[i] = false;
	}
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	inq[s] = true;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = false;
		for (int i = head[u]; ~i; i = e[i].next) {
			int v = e[i].to, w = e[i].w;
			if (dis[u] + w < dis[v]) {
				dis[v] = dis[u] + w;
				if (!inq[v]) {
					inq[v] = true;
					q.push(v);
					Neg[v]++;
					if (Neg[v] > n)
						return 1;
				}
			}
		}
	}
	return 0;
}

signed main() {
	scanf("%d%d%d", &n, &m1, &m2);
	init();
	for (int i = 1; i < n; i++)
		addedge(0, i, 0), addedge(i, i + 1, 0);
	addedge(0,n,0);
	for (int i = 1; i <= m1; i++) {
		int a, b, d;
		scanf("%d%d%d", &a, &b, &d);
		addedge(a, b, d);
	}
	for (int i = 1; i <= m2; i++) {
		int a, b, d;
		scanf("%d%d%d", &a, &b, &d);
		addedge(b, a, -d);
	}
	if (spfa(0))
		printf("-1");
	else {
		if (dis[n] = inf)
			printf("-2");
		else
			printf("%d", dis[n]);
	}
	return 0;
}
2024/10/2 21:53
加载中...