代码如下

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

const int N = 1e5 + 5;

int n, m, f[N], l[N], e[N], tag[N];

vector<int> adja[N];

void dfs(int idx)
{
	if(tag[idx] >= 1) return;
	tag[idx]++;
	for(size_t i = 0; i < adja[idx].size(); i++) {
		if(l[adja[idx][i]] > l[idx]) {
			l[adja[idx][i]] = l[idx];
		}
		if(e[adja[idx][i]] < e[idx] || e[adja[idx][i]] < (f[adja[idx][i]] - l[adja[idx][i]])) {
			e[adja[idx][i]] = max(e[idx], f[adja[idx][i]] - l[adja[idx][i]]);
		}
		dfs(adja[idx][i]);
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &f[i]);
		l[i] = f[i];
		//e[i] = 0; 
	}
	int u, v, z;
	for(int i = 0; i < m; i++) {
		scanf("%d%d%d", &u, &v, &z);
		adja[u].push_back(v);
		if(z == 2)
			adja[v].push_back(u);
	}
	
	dfs(1);
	
	printf("%d\n", e[n]);
	
	return 0;
} 

本来我的dfs函数是这样的：

void dfs(int idx)
{
	bool flag = false;
	for(size_t i = 0; i < adja[idx].size(); i++) {
		if(l[adja[idx][i]] > l[idx]) {
			l[adja[idx][i]] = l[idx];
			flag = true;
		}
		if(e[adja[idx][i]] < e[idx] || e[adja[idx][i]] < (f[adja[idx][i]] - l[adja[idx][i]])) {
			e[adja[idx][i]] = max(e[idx], f[adja[idx][i]] - l[adja[idx][i]]);
			flag = true;
		}
		if(flag) dfs(adja[idx][i]);
	}
}

不知道为什么在一个点对前文数据没有任何更新的情况下仍然需要从这个点向后进行搜索更新，不然无法到达点n 求dalao解释