P4878 [USACO05DEC] Layout G 79分求调

#include<bits/stdc++.h>
using namespace std;
int n;
int ml;
int md;
int u, v, w;
struct edge {
	int u, v, w;
};
vector<edge> adj[1005];
int inq[1005], cnt[1005], dis[1005];

bool SPFA(int start) {
	memset(dis, 0x3f, sizeof(dis));
	memset(cnt, 0, sizeof(cnt));
	queue<int> q;
	q.push(start);
	dis[start] = 0;
	inq[start] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		inq[u] = 0;
		for (auto e : adj[u]) {
			if (dis[e.v] > dis[u] + e.w) {
				dis[e.v] = dis[u] + e.w;
				cnt[e.v] = cnt[u] + 1;
				if (cnt[e.v] >= n) return true;
				if (!inq[e.v]) q.push(e.v), inq[e.v] = 1;
			}
		}
	}
	return false;
}

int main() {
	cin >> n >> ml >> md;
	for (int i = 1; i <= ml; i++) {
		cin >> u >> v >> w;
		adj[u].push_back({u, v, w});
	}
	for (int i = 1; i <= md; i++) {
		cin >> u >> v >> w;
		adj[v].push_back({v, u, -w});
	}
	for (int i = 1; i < n; i++) {
		adj[i + 1].push_back({i + 1, i, 0});
	}
	if (SPFA(1)) {
		cout << "-1";
	} else if (dis[n] == 0x3f) {
		cout << "-2";
	} else {
		cout << dis[n] - dis[1];
	}
	return 0;
}