首先这是个图，而且能无限走点，所以缩点。因为要求最大利润，所以要求一条路径上后方地点售价和前方地点售价的差的最大值。

对于一个缩点，保留两个值：点内售价的最大值和最小值。用拓扑DP跑一遍，可以求出到达每个点时能获得的最低售价。

最后统计答案，对于所有点，用点内最大值减去到达这个点时的最小值，然后取最大值。

思路大概没有问题吧？WA了，20分，讨论区那位大佬的hack数据能过。（这题有点像劫掠计划。

附上码，请救救我我我的码。

#include <bits/stdc++.h>
using namespace std;

int n, m, ans;

int hd[100001], fm[100001], to[100001], cnt;
int vl[100001];

void add(int x, int y) {
	++cnt;
	fm[cnt] = hd[x];
	to[cnt] = y;
	hd[x] = cnt;
}

int hd_[100001], fm_[100001], to_[100001], cnt_;
int mx[100001], mn[100001];

void add_(int x, int y) {
	++cnt_;
	fm_[cnt_] = hd_[x];
	to_[cnt_] = y;
	hd_[x] = cnt_;
}

int dfn[100001], low[100001], num;
int cl[100001], cln;
int st[100001], top;
bool in[100001];

void tarjan(int u) {
	dfn[u] = low[u] = ++num;
	st[++top] = u; in[u] = 1;
	
	for (register int p = hd[u]; p; p = fm[p]) {
		int v = to[p];
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
			
		} else if (in[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	
	if (low[u] == dfn[u]) {
		int k;
		++cln;
		do {
			k = st[top--];
			in[k] = 0;
			
			cl[k] = cln;
			mn[cln] = min(mn[cln], vl[k]);
			mx[cln] = max(mx[cln], vl[k]);
			
		} while (k != u);
	}
}

map<int, map<int, bool> >flag;
int rd[100001];

void link(int u) {
	for (register int p = hd[u]; p; p = fm[p]) {
		int v = to[p];
		if (cl[u] != cl[v] && !flag[cl[u]][cl[v]]) {
			flag[cl[u]][cl[v]] = 1;
			add_(cl[u], cl[v]);
			++rd[cl[v]];
		}
	}
}

void dp() {
	queue<int>q;
	q.push(cl[1]);
	
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (register int p = hd_[u]; p; p = fm_[p]) {
			int v = to_[p];
			mn[v] = min(mn[v], mn[u]);
			--rd[v];
			if (!rd[v]) q.push(v);
		}
	}
	
	for (register int i = 1; i <= cln; ++i) {
		ans = max(ans, mx[i] - mn[i]);
	}
	
	ans =  max(ans, 0);
}

void read() {
	scanf("%d%d", &n, &m);
	
	for (register int i = 1; i <= n; ++i) {
		scanf("%d", &vl[i]);
	}
	
	for (register int i = 1; i <= m; ++i) {
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		if (z == 1) {
			add(x, y);
		} else {
			add(x, y);
			add(y, x);
		}
	}
}

signed main(void) {
	read();
	
	for (register int i = 1; i <= n; ++i) mn[i] = 100000;
	tarjan(1);
	
	for (register int i = 1; i <= n; ++i) {
		if (cl[i]) link(i);
	}
	
	dp();
	
	printf("%d", ans);
	return 0;
}