50分求助

#include <bits/stdc++.h>
using namespace std;
int m,n,cnt,low[1000005],dfn[1000005],f[1000005],a[1000005],cnt2,c[1000005],dp[1000005][2],vis[1000005];
int k,x,y;
vector<int> e[1000005];
stack<int> s;
struct node{
	int maxx,minn;
}o[1000005];
queue<int> q;
void tarjan(int x){
	low[x]=dfn[x]=++cnt;
	vis[x]=1;
	s.push(x);
	for(int i=0;i<e[x].size();i++){
		if(!dfn[e[x][i]]){
			tarjan(e[x][i]);
			low[x]=min(low[x],low[e[x][i]]);
		}else{
			if(vis[e[x][i]]) {
				low[x]=min(low[x],low[e[x][i]]);
				
			}
		}
	}
	
	if(low[x]==dfn[x]){
		++cnt2;
		o[cnt2].maxx=-1000;
		o[cnt2].minn=1000;
		while(1){
			f[s.top()]=cnt2;
			o[cnt2].maxx=max(o[cnt2].maxx,a[s.top()]);
			o[cnt2].minn=min(o[cnt2].minn,a[s.top()]);
			vis[s.top()]=0;
			if(s.top()==x){
				s.pop();
				break;
			}
			s.pop();
		}
		
	}
}
int main(){
	scanf("%d%d",&n,&m);
	cnt2=n;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&k);
		e[x].push_back(y);
		if(k==2) e[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i]){
			tarjan(i);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=0;j<e[i].size();j++){
			e[f[i]].push_back(f[e[i][j]]);
			c[f[e[i][j]]]++;
		}
	}
	q.push(f[1]);
	for(int i=n+1;i<=cnt2;i++){
		dp[i][1]=o[i].minn;
		dp[i][0]=o[i].maxx-o[i].minn;
	}
	while(!q.empty()){
		int v=q.front();
		q.pop();
		for(int i=0;i<e[v].size();i++){
			c[e[v][i]]--;
			dp[e[v][i]][1]=min(dp[e[v][i]][1],dp[v][1]);
			dp[e[v][i]][0]=max(max(dp[e[v][i]][0],o[e[v][i]].maxx-dp[e[v][i]][1]),dp[v][0]);
			if(c[e[v][i]]==0){
				q.push(e[v][i]);
			}
		}
	}
//	for(int i=n+1;i<=cnt2;i++){
//		cout<<dp[i][1]<<endl;
//	}
	cout<<dp[f[n]][0];
	return 0;
}