差分约束 37 pts 求助
查看原帖
差分约束 37 pts 求助
688783
SilverLi楼主2023/11/1 17:32
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 5e3 + 5;
int n, ml, md, dis[N];
int T, vis[N], v[N];
vector<int> g[N], W[N];
// SPFA
inline bool dij(int s) {
	memset(v, 0, sizeof(v));
    memset(vis, 0, sizeof(vis));
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	queue<int> q;
	q.push(s);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		v[u] = 0;
		for (int l = 0; l < g[u].size(); ++l) {
			int i = g[u][l], w = W[u][l];
			if (dis[i] > dis[u] + w) {
				dis[i] = dis[u] + w;
				if (!v[i]) {
					if (++vis[i] > n) return 1;
					q.push(i);
					v[i] = 1;
				}
			}
		}
	}
	return 0;
}
signed main() {
	cin >> n >> ml >> md;
	while (ml--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[v].emplace_back(u);
		W[v].emplace_back(w);
	}
	while (md--) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u].emplace_back(v);
		W[u].emplace_back(-w);
	}
	for (int i = 1; i < n; ++i) {
		g[i].emplace_back(i + 1);
		W[i].emplace_back(1);
	}
	int root = 0;
	for (int i = 1; i <= n; ++i) {
		g[root].emplace_back(i);
		W[root].emplace_back(0);
	}
	if (dij(root))	puts("-1");
	else {
		g[root].clear(); W[root].clear();
		int rt = 1;
		dij(rt);
		if (dis[n] == 0x3f3f3f3f)
			dis[n] = -2;
		cout << dis[n] << '\n';
	}
	return 0;
}
/*
di[a] - di[b] <= d
di[a] <= di[b] + d

di[a] - di[b] >= d
di[b] <= di[a] - d
*/
2023/11/1 17:32
加载中...