差分约束代码

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
typedef long long ll;
using namespace std;

const int N = 1e5 + 10;
int n, m1, m2, dis[N], cnt[N];
bool vis[N];
vector<pair<int, int> > graph[N];

queue<int> q;
bool spfa(int s)
{
	memset(dis, 63, sizeof dis);
	dis[s] = 0;
	q.push(s);
	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		vis[u] = false;
		for (auto i : graph[u])
		{
			int v = i.first, w = i.second;
			if (dis[v] > dis[u] + w)
			{
				dis[v] = dis[u] + w;
				if (!vis[v])
				{
					q.push(v);
					vis[v] = true;
					cnt[v]++;
				}
			}
			if (cnt[v] > n) return false;
		}
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m1 >> m2;
	for (int i = 1; i <= m1; i++)
	{
		int a, b, d;
		cin >> a >> b >> d;
		graph[a].push_back(make_pair(b, d));
	}
	
	for (int i = 1; i <= m2; i++)
	{
		int a, b, d;
		cin >> a >> b >> d;
		graph[b].push_back(make_pair(a, -d));
	}
	
	for (int i = 1; i < n; i++)
	{
		graph[i + 1].push_back(make_pair(i, 0));
	}
	
	bool k = spfa(1);
	
	if (!k) cout << -1 << endl;
	else if (dis[n] == 0x3f3f3f3f) cout << -2 << endl;
	else cout << dis[n] << endl;
	return 0;
}