能有不用链式前项星的优化思路吗,代码已经足够臃肿了
-_-

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

#define LL long long
#define pb emplace_back
#define fr first
#define sc second
typedef const int Int;
typedef pair<int,int> pii;

Int N=1e5+5;

vector <int> G[N];
vector <int> F[N];
vector <int> fF[N];
queue <int> Q;
bool vis[N];

int n,m;

int A[N];
int minn[N],maxn[N];

bool insta[N];
int sta[N],dfn[N],low[N],h,cnt;
int bel[N],bcnt;

int from,to;

inline void Rcd(Int &x){
	insta[x]=false;
	bel[x]=bcnt;
	if(x==1)from=bcnt;
	if(x==n)to=bcnt;
}

void dfs(Int &u){
	dfn[u]=low[u]=++cnt,sta[++h]=u,insta[u]=true;
	for(Int &v:G[u]){
		if(!dfn[v]){
			dfs(v);
			low[u]=min(low[u],low[v]);
		}
		else if(insta[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		bcnt++;
		while(sta[h]^u)Rcd(sta[h--]);
		h--,Rcd(u);
	}
}

void mrk(Int &s){
	queue <int> q;
	q.push(s);
	while(!q.empty()){
		int u=q.front();
		vis[u]=true,q.pop();
		for(Int &v:fF[u])if(!vis[v])q.push(v);
	}
}

int ans;

int main(){
	memset(minn,0x3f,sizeof(minn));
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",&A[i]);
	for(int i=1;i<=m;i++){
		int u,v,t;
		scanf("%d%d%d",&u,&v,&t);
		if(t==2)G[v].pb(u);
		G[u].pb(v);
	}
	for(int i=1;i<=n;i++)if(!dfn[i])dfs(i);
	for(int i=1;i<=n;i++){
		for(Int &v:G[i])if(!vis[v]&&bel[i]^bel[v])F[bel[i]].pb(bel[v]),fF[bel[v]].pb(bel[i]),vis[v]=true;
		for(Int &v:G[i])vis[v]=false;
		G[i].clear();
		minn[bel[i]]=min(minn[bel[i]],A[i]),maxn[bel[i]]=max(maxn[bel[i]],A[i]);
	}
	mrk(to);
	Q.push(from);
	while(!Q.empty()){
		int u=Q.front();
		Q.pop();
		ans=max(ans,maxn[u]-minn[u]);
		for(Int &v:F[u]){
			minn[v]=min(minn[u],minn[v]);
			if(vis[v])Q.push(v);
		}
	}
	printf("%d",ans);
	return 0;
}

为什么只给125MiB啊QAQ