有份错误的代码可以AC。

输入

5 6
1 2 3 4 5
1 2 1
2 4 1
4 1 1
3 1 1
3 4 1
4 5 1

正确输出应该为4，但这份代码却输出3

#include <bits/stdc++.h>
using namespace std;
const int N=1e5+5,INF=1e9;
int n,m,ti,cnt,a[N],dp[N],sum[N],dfn[N],low[N],scc[N],last[N];
int r[N],del[N],mi[N],mx[N],vis[N],vis2[N];
queue<int> q;
vector<int> G[N],ed[N],E[N];
stack<int> S;
void tarjan(int u) {
	dfn[u]=low[u]=++ti;
	S.push(u);
	for (auto v:ed[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if (!scc[v])
			low[u]=min(low[u],dfn[v]);
	}
	if (dfn[u]==low[u]) {
		cnt++;
		mi[cnt]=INF;
		while (true) {
			int v=S.top();
			S.pop();
			scc[v]=cnt;
			mi[cnt]=min(mi[cnt],a[v]);
			mx[cnt]=max(mx[cnt],a[v]);
			if (v==u) break;
		}
	}
}
void bfs(int st,int *nowv,vector<int> *g) {
	while (!q.empty()) q.pop();
	q.push(st);
	nowv[st]=1;
	while (!q.empty()) {
		int u=q.front();
		q.pop();
		for (auto v:g[u]) {
			if (nowv[v]) continue;
			nowv[v]=1;
			q.push(v);
		}
	}
}
int main() {
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	for (int i=1;i<=m;i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		ed[x].push_back(y);
//		if (x!=1&&y==1) vis[x]=1;
		if (z==2) {
			ed[y].push_back(x);
//			if (y!=1&&x==1) vis[y]=1;
		}
	}
	for (int i=1;i<=n;i++)
		if (!scc[i]) tarjan(i);
	for (int i=1;i<=n;i++)
		for (auto v:ed[i])
			if (scc[i]!=scc[v]) {
				E[scc[i]].push_back(scc[v]);
				G[scc[v]].push_back(scc[i]);
				r[scc[v]]++;
			}
	bfs(scc[1],vis,E);
	bfs(scc[n],vis2,G);
	while (!q.empty()) q.pop();
	for (int i=1;i<=cnt;i++)
		if (!r[i]&&vis[i]) q.push(i);
	for (int i=1;i<=cnt;i++)
		dp[i]=mx[i]-mi[i];
//	printf("%d\n",scc[1]);
	while (!q.empty()) {
		int ft=q.front();
		q.pop();
		for (auto v:E[ft]) {
			r[v]--;
			if (!r[v]&&vis2[v]) q.push(v);
			mi[v]=min(mi[v],mi[ft]);
			dp[v]=max({dp[v],mx[v]-mi[ft],dp[ft]});
//			printf("%d %d %d\n",ft,v,mi[v]);
		}
	}
	int ans=0;
	for (int i=1;i<=cnt;i++)
		if (vis[i]&&vis2[i]) ans=max(ans,dp[i]);
	printf("%d\n",ans);
	return 0;
}