Cod sursă (job #368980)

#include <bits/stdc++.h>

using namespace std;

ifstream in("dragoni.in");
ofstream out("dragoni.out");

struct lol{
	int nod, dist, mx;
};

int p, n, m, x, y, c, bst, pw[8010], dp[8010], pmx[8010], pmx2[8010];
vector <pair <int, int> > v[8010];
bool viz[8010];
queue <lol> q;
lol w;

void dfs(int from, int cur){
	bst = max(bst, pw[from]);
	viz[from] = 1;
	for(auto to : v[from])
		if(!viz[to.first] && cur >= to.second)
			dfs(to.first, cur);
}

void solve(){
	for(int i = 1; i <= n; i++)
		dp[i] = 2e9, pmx[i] = pmx2[i] = 0;
	dp[1] = 0;
	pmx[1] = pw[1];
	q.push({1, 0, pw[1]});
	while(!q.empty()){
		w = q.front();
		q.pop();
		for(auto cur : v[w.nod])
			if(w.mx >= cur.second){
				if(w.dist + cur.second < dp[cur.first]){
					dp[cur.first] = w.dist + cur.second;
					q.push({cur.first, dp[cur.first], pmx[cur.first] = max(w.mx, pw[cur.first])});
					continue;
				}
				if(w.mx > pmx2[cur.first])
					q.push({cur.first, w.dist + cur.second, pmx2[cur.first] = w.mx});
			}
	}
	out << dp[n];
}

int main(){
	in >> p;
	in >> n >> m;
	for(int i = 1; i <= n; i++)
		in >> pw[i];
	for(int i = 1; i <= m; i++){
		in >> x >> y >> c;
		v[x].push_back({y, c});
		v[y].push_back({x, c});
	}
	if(p == 1){
		dfs(1, pw[1]);
		return out << bst, 0;	
	} 
	solve();
	return 0;
}