哪位大佬救一下

MLE代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, b[200005], dis[200005];
struct node{
	ll v, w;
};
vector <node> adj[200005];
bool check(ll mid){
	queue <ll> q;
	q.push(1);
	for(ll i = 1; i <= n; i++) dis[i] = -1;
	if(b[1] < mid) dis[1] = b[1];
	else dis[1] = mid;
	while(!q.empty()){
		ll u = q.front();
		q.pop();
		for(ll i = 0; i < adj[u].size(); i++){
			ll v = adj[u][i].v, w = adj[u][i].w;
			if(dis[u] == -1) continue;
			if(dis[u] >= w){
				q.push(v);
				if(b[v] + dis[u] < mid) dis[v] = b[v] + dis[u];
				else dis[v] = mid;
			}
		}
	}
	if(dis[n] == -1) return 0;
	else if(dis[n] <= mid) return 1;
	else return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--){
		cin >> n >> m;
		for(ll i = 1; i <= n; i++) adj[i].clear();
		for(ll i = 1; i <= n; i++) b[i] = 0;
		ll l = 0, r = 0;
		for(ll i = 1; i <= n; i++){
			cin >> b[i];
			r += b[i];
		}
		for(ll i = 1; i <= m; i++){
			ll u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back({v, w});
		}
		ll ans = -1;
		while(l <= r){
			ll mid = (l + r) / 2;
			if(check(mid)){
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		cout << ans << endl;
	}
	return 0;
}

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t, n, m, b[200005], dis[200005];
struct node{
	ll v, w;
};
vector <node> adj[200005];
bool check(ll mid){
//	queue <ll> q;
//	q.push(1);
	for(ll i = 1; i <= n; i++) dis[i] = -1;
	if(b[1] < mid) dis[1] = b[1];
	else dis[1] = mid;
//	while(!q.empty()){
//		ll u = q.front();
//		q.pop();
//		for(ll i = 0; i < adj[u].size(); i++){
//			ll v = adj[u][i].v, w = adj[u][i].w;
//			if(dis[u] == -1) continue;
//			if(dis[u] >= w){
//				q.push(v);
//				if(b[v] + dis[u] < mid) dis[v] = b[v] + dis[u];
//				else dis[v] = mid;
//			}
//		}
//	}
	for(ll i = 1; i <= n; i++){
		for(ll j = 0; j < adj[i].size(); j++){
			ll v = adj[i][j].v, w = adj[i][j].w;
			if(dis[i] == -1) continue;
			if(dis[i] >= w){
				if(b[v] + dis[i] < mid) dis[v] = b[v] + dis[i];
				else dis[v] = mid;
			}
		}
	}
	if(dis[n] == -1) return 0;
	else if(dis[n] <= mid) return 1;
	else return 0;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> t;
	while(t--){
		cin >> n >> m;
		for(ll i = 1; i <= n; i++) adj[i].clear();
		for(ll i = 1; i <= n; i++) b[i] = 0;
		ll l = 0, r = 0;
		for(ll i = 1; i <= n; i++){
			cin >> b[i];
			r += b[i];
		}
		for(ll i = 1; i <= m; i++){
			ll u, v, w;
			cin >> u >> v >> w;
			adj[u].push_back({v, w});
		}
		ll ans = -1;
		while(l <= r){
			ll mid = (l + r) / 2;
			if(check(mid)){
				ans = mid;
				r = mid - 1;
			}
			else l = mid + 1;
		}
		cout << ans << endl;
	}
	return 0;
}

不理解为什么

已红温