这组数据

3 2
100 1 100
2 1 1
1 3 1

会让

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1e5 + 10, M = 1e6 + 10;
int dfn[N], col[N], low[N], stk[N], top, tim, ccn, n, m, q, a[N], minv[N], maxv[N], deg[2][N], I1, In;
bool ins[N], vis[2][N], ok[2][N];
vector <int> G[N];
set <int> gg[2][N];
struct Edge {
	int u, v;
} E[M];
void Tarjan(int x) {
    dfn[x] = low[x] = ++tim;
    stk[++top] = x, ins[x] = 1;
    for(const auto y : G[x]) {
        if(!dfn[y]) {
            Tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (ins[y])
            low[x] = min(low[x], dfn[y]);
    }
    if(dfn[x] == low[x]) {
        int y;
		ccn++;
        do {
            y = stk[top--];
            ins[y] = 0, col[y] = ccn;
        } while(x != y);
    }
}
bool Dfs1(int u) {
	if(u == In) return 1;
	if(vis[0][u]) return ok[0][u];
	vis[0][u] = 1;
	for(const auto& v : gg[0][u]) {
		bool flg = Dfs1(v);
		ok[0][u] |= flg;
		if(flg)
			maxv[u] = max(maxv[u], maxv[v]);
	}
	if(!ok[0][u]) maxv[u] = 0;
	return ok[0][u];
}
bool Dfs2(int u) {
	if(u == I1) return 1;
	if(vis[1][u]) return ok[1][u];
	vis[1][u] = 1;
	for(const auto& v : gg[1][u]) {
		bool flg = Dfs2(v);
		ok[1][u] |= flg;
		if(flg)
			minv[u] = min(minv[u], minv[v]);
	}
	if(!ok[1][u]) minv[u] = 0x3f3f3f3f;
	return ok[1][u];
}
int main() {
	memset(minv, 0x3f, sizeof(minv));
	cin >> n >> m;
	for(int i=1; i<=n; i++) cin >> a[i];
	for(int i=1; i<=m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		G[u].push_back(v);
		E[++q] = {u, v};
		if(--w) {
			G[v].push_back(u);
			E[++q] = {v, u};
		}
	}
	for(int i=1; i<=n; i++) {
		if(!dfn[i]) Tarjan(i);
	}
	for(int i=1; i<=n; i++) {
		minv[col[i]] = min(minv[col[i]], a[i]);
		maxv[col[i]] = max(maxv[col[i]], a[i]);
	}
	I1 = col[1];
	In = col[n];
	for(int i=1; i<=q; i++) {
		gg[0][col[E[i].u]].insert(col[E[i].v]);
		gg[1][col[E[i].v]].insert(col[E[i].u]);
		++deg[0][col[E[i].v]];
		++deg[1][col[E[i].u]];
	}
	for(int i=1; i<=ccn; i++) {
		if(!deg[0][i]) Dfs1(i); //i -> n max
		if(!deg[1][i]) Dfs2(i); //1 -> i min
	}
	int res = 0;
	for(int i=1; i<=ccn; i++) {
		res = max(res, maxv[i] - minv[i]);
	}
	cout << res << endl;
}

这份代码输出 99，但正解是 0。

@Maxmilite @E_Space @离散小波变换°