#include<iostream>
using namespace std;
const int N = 1e5 + 5,inf = 0x3f3f3f3f;

struct edge{
	int nxt,to;
}e[5*N];
int n,m,x,y,z,p[N],path[N],ans,vis[N],tot,head[N];

void add(int u,int v){
	e[tot].to = v,e[tot].nxt = head[u],head[u] = tot ++;
}

void dfs(int u,int num){
	path[num] = u;
	if(u == n){
		int minn = inf,maxx = 0;
		for(int i=1;i<=num;i++){
			minn = min(minn,p[path[i]]);
			maxx = max(maxx,p[path[i]] - minn);
		}
		
		ans = max(maxx,ans);
	}
	
    vis[u] ++;
	for(int i=head[u];i!=-1;i=e[i].nxt){
	    int v = e[i].to;
		if(vis[v] <= 5) dfs(v,num + 1);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&p[i]);
	for(int i=1;i<=n;i++)head[i] = -1;
	
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		add(x,y);
	    if(z == 2) add(y,x);	
	}
	
	dfs(1,1);
	cout << ans << endl;
	return 0;
}

各位请看第27行那个vis[u]++,根本就没有回溯（应该在结束时vis[u]--），我当时忘了。

我一开始第30行写的是vis[u]<=2,竟然有70，3个wa，然后我把回溯加上结果只有20。。。

然后我尝试将 <=2 扩大，当扩大到 <=5时就ac了，不知道csp考试时这种做法可不可取