P1073 [NOIP2009 提高组] 最优贸易

这题样例我代码输出2，但是正确答案是5

本来想看看交上去能得几分的，结果直接A了

#include <iostream>
#include <queue>
using namespace std;
#define N 100005
#define M 20 * N

int head[N], rhead[N], ver[M], Next[M], n, m, tot;
int key[N];	// Prices of glow balls
void ADD(int *arr, int x, int y, int z){
	ver[++tot] = y;
	Next[tot] = arr[x];
	arr[x] = tot;
}


int small[N], big[N];
bool vis[N];
queue<int> Q;
void SPFAsmall(int root){
	fill(small, small + N, 0x3f3f3f3f);
	fill(vis, vis + N, 0);
	small[root] = key[root];
	Q.push(root);
	vis[root] = 1;
	while(!Q.empty()){
		int x = Q.front();
		Q.pop();
		vis[x] = 0;
		for(int i = head[x]; ~i; i = Next[i]){
			int y = ver[i];
			if(small[y] > min(small[x], key[y])){
				small[y] = min(small[x], key[y]);
				if(vis[y] == false){
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
}
void SPFAbig(int root){
	fill(big, big + N, 0);
	fill(vis, vis + N, 0);
	big[root] = key[root];
	Q.push(root);
	vis[root] = 1;
	while(!Q.empty()){
		int x = Q.front();
		Q.pop();
		vis[x] = 0;
		for(int i = rhead[x]; ~i; i = Next[i]){
			int y = ver[i];
			if(big[y] < max(big[x], key[y])){
				big[y] = max(big[x], key[y]);
				if(vis[y] == false){
					Q.push(y);
					vis[y] = 1;
				}
			}
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int x, y, z;
	fill(head, head + N, -1);
	fill(rhead, rhead + N, -1);
	tot = -1;
	scanf("%d%d", &n, &m);
	for(int i = 1; i <= n; ++ i)
		scanf("%d", &key[i]);
	for(int i = 1; i <= m; ++ i){
		scanf("%d%d%d", &x, &y, &z);
		ADD(head, x, y, z);
		ADD(rhead, y, x, z);
	}
	
	SPFAsmall(1);	// small
	SPFAbig(n);		// big
	
	int ans = 0;
	for(int i = 1; i <= n; ++ i){
		ans = max(ans, big[i] - small[i]);
//		cout << big[i] << ' ' << small[i] << endl;
	}
	cout << ans << endl;
	
	return 0;
}

有没有dalao帮忙看看qwq