$2TLE$ $1MLE$ 代码如下

#include <iostream>
#include <stack>
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int n, m, cnt, tot, num, p[100005], head[100005], dfn[100005], low[100005], d[100005], size[100005];
bool vis[100005];
int head2[100005], minp[100005], maxp[100005], in[100005], earn[100005];
stack<int> s;
struct edge {
	int v, next;
} e[500005], e2[500005];
struct edge2 {
	int u, v;
	bool operator == (edge2& b) const {
		return u == b.u && v == b.v;
	}
} e3[500005];
void add(int u, int v) {
	e[++cnt].v = v;
	e[cnt].next = head[u];
	head[u] = cnt;
}
void add2(int u, int v) {
	e2[++cnt].v = v;
	e2[cnt].next = head2[u];
	head2[u] = cnt;
	//cerr << u << ' ' << v << ' ' << cnt << '\n';
}
bool cmp(edge2 a, edge2 b) {
	if (a.v != b.v)
		return a.v < b.v;
	return a.u < b.u;
}
void tarjan(int x) {
	dfn[x] = low[x] = ++tot;
	s.push(x);
	vis[x] = 1;
	for (int i = head[x]; i; i = e[i].next) {
		int v = e[i].v;
		if (!dfn[v]) {
			tarjan(v);
			low[x] = min(low[x], low[v]);
		} else if (vis[v])
			low[x] = min(low[x], dfn[v]);
	}
	if (dfn[x] == low[x]) {
		vis[x] = 0;
		d[x] = ++num;
		size[num] = 1;
		maxp[num] = minp[num] = p[x];
		while (s.top() != x) {
			d[s.top()] = num;
			vis[s.top()] = 0;
			maxp[num] = max(maxp[num], p[s.top()]);
			minp[num] = min(minp[num], p[s.top()]);
			++size[num];
			s.pop();
		}
		s.pop();
		in[num] = minp[num];
		earn[num] = maxp[num] - in[num];
	}
}
void bfs(int x) {
	queue<int> q;
	q.push(x);
	while (!q.empty()) {
		int u = q.front();
		for (int i = head2[u]; i; i = e2[i].next) {
			int v = e2[i].v;
			//printf("%d %d || %d %d %d %d || %d %d %d %d\n", u, v, minp[u], maxp[u], minp[v], maxp[v], in[u], earn[u], in[v], earn[v]);
			in[v] = min(in[v], in[u]);
			earn[v] = max(earn[v], max(earn[u], maxp[v] - in[v]));
			q.push(v);
		}
		q.pop();
	}
}
int main() {
	int x, y, z, cnt2 = 0, ans = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		scanf("%d", &p[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &x, &y, &z);
		add(x, y);
		if (z == 2)
			add(y, x);
	}
	cnt = 0;
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) {
			tarjan(i);
		}
	for (int i = 1; i <= n; i++) {
		for (int j = head[i]; j; j = e[j].next)
			if (d[i] != d[e[j].v]) {
				e3[++cnt2].u = d[i];
				e3[cnt2].v = d[e[j].v];
			}
	}
	sort(e3 + 1, e3 + 1 + cnt2, cmp);
	cnt = unique(e3 + 1, e3 + 1 + cnt2) - e3;
	for (int i = 1; i <= cnt2; i++)
		add2(e3[i].u, e3[i].v);
	bfs(d[1]);
	printf("%d", max(0, earn[d[n]]));
	return 0;
}

求 $dalao$ 解答