我用缩点+拓扑打的

两个问题求解答：

1. 缩点完后拓扑为什么要从 $1$ 号点开始而不是从入度为 $0$ 的点开始跑。

2. 求调代码。

#include<bits/stdc++.h>
using namespace std;
#define N 500005
int n,m,m1,i,j,ans,k1,k2,a,b,opt,flag,sta;
int dis[N],h1[N],h2[N],dfn[N],low[N],col[N],st[N],se[N],bu[N],s[N],ru[N],u[N];
int cnt,sum,num,step;
struct AB{
	int a,b,n;
}d[N*2],p[N*2];
void cun1(int a,int b){
	d[++k1].a=a,d[k1].b=b;
	d[k1].n=h1[a],h1[a]=k1;
}
void cun2(int a,int b){
	p[++k2].a=a,p[k2].b=b;
	p[k2].n=h2[a],h2[a]=k2;
}
queue<int>q;
void Tarjan(int a){
	low[a]=dfn[a]=++num;
	st[++step]=a;
	for(int i=h1[a];i;i=d[i].n){
		int b=d[i].b;
		if(!dfn[b]){
			Tarjan(b);
			low[b]=min(low[b],low[a]);
		}
		else if(!col[b]) low[a]=min(low[a],dfn[b]);
	}
	if(low[a]==dfn[a]){
		col[a]=++cnt;
		if(a==n) flag=cnt;
		if(a==1) sta=cnt;
		se[cnt]=bu[cnt]=s[a];
		while(st[step]!=a){
			if(st[step]==n) flag=cnt;
			if(st[step]==1) sta=cnt;
			col[st[step]]=cnt;
			se[cnt]=max(se[cnt],s[st[step]]),bu[cnt]=min(bu[cnt],s[st[step]]);
			step--;
		}
		dis[cnt]=max(dis[cnt],se[cnt]-bu[cnt]);
		step--;
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) scanf("%d",&s[i]);
	for(i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&opt);
		cun1(a,b),m1++;
		if(opt==2) cun1(b,a),m1++;
	}
	for(i=1;i<=n;i++){
		if(!dfn[i]) Tarjan(i);
	}
	for(i=1;i<=m1;i++){
		if(col[d[i].a]!=col[d[i].b]) cun2(col[d[i].a],col[d[i].b]),ru[d[i].b]++;
	} 
	q.push(sta);
	while(!q.empty()){
		a=q.front(),q.pop();
		for(i=h2[a];i;i=p[i].n){
			b=p[i].b;
			bu[b]=min(bu[b],bu[a]);
			dis[b]=max(dis[b],max(dis[a],se[b]-bu[b]));
			ru[b]--;
			if(!ru[b]) q.push(b);
		}
	}
	printf("%d",dis[flag]);
	return 0;
}