P1073 最优贸易

#include <bits/stdc++.h>
using namespace std;
struct node {
	int id, dis;
};
vector<node> a[30005];
queue<int> q;
int n, m, w[300005], u, v, t, dis;
bool f[300005];

void spfa() {
	memset(w, -0x3f, sizeof(w));
	w[1] = 0;
	q.push(1);
	while (!q.empty()) {
		u = q.front(), q.pop();
		f[u] = 0;
		for (int i = 0; i < a[u].size(); i ++) {
			v = a[u][i].id, dis = w[u] + a[u][i].dis;
			if (dis <= w[v]) continue;
			w[v] = dis;
			if (!f[v]) q.push(v), f[v] = 1;
		}
	}
}

int main()
{
	cin >> n >> m;
	int n2 = n * 2;
	for (int i = 1; i <= n; i ++) {
		cin >> t;
		a[i].push_back({n + i, -t});
		a[n + i].push_back({n2 + i, t});
	}
	for (int i = 1; i <= m; i ++) {
		cin >> u >> v >> t;
		a[u].push_back({v, 0});
		a[n + u].push_back({n + v, 0});
		a[n2 + u].push_back({n2 + v, 0});
		if (t == 2) {
			a[v].push_back({u, 0});
			a[n + v].push_back({n + u, 0});
			a[n2 + v].push_back({n2 + u, 0});
		}
	}
	spfa();
	cout << w[3 * n];
	return 0;
 }