Cod sursă (job #369435)

#include<bits/stdc++.h>
#define NMAX 810
#define x first
#define y second

using namespace std;

struct nod {
	int x,g,c;
};

vector<int>V1[NMAX];
vector<pair<int,int> >V[NMAX];
int rs,p,n,m;
bool viz[NMAX];
int b[NMAX];
pair<int,int> d[NMAX];
queue<nod>Q;

void DFS(int x) {
	viz[x]=1;rs=max(rs,b[x]);
	for (int i=0; i<V1[x].size(); i++) {
		if (!viz[V1[x][i]]) {
			DFS(V1[x][i]);
		}
	}
}

int main() {
	ifstream cin("dragoni2.in");
	ofstream cout("dragoni2.out");
	cin>>p>>n>>m;
	if (p==1) {
		for (int i=1; i<=n; i++) {
			cin>>b[i];
		}
		
		for (int i=1; i<=m; i++) {
			int x,y,c; cin>>x>>y>>c;
			if (c>b[1]) continue;
			else{
				V1[x].push_back(y);
				V1[y].push_back(x);
			}
		}
		
		DFS(1);
		cout<<rs;
		return 0;
	} 
	for (int i=1; i<=n; i++) cin>>b[i];
	
	for (int i=1; i<=m; i++) {
		int x,y,c; cin>>x>>y>>c;
		V[x].push_back({y,c});
		V[y].push_back({x,c});
	}
	for (int i=1; i<=n; i++) cin>>b[i], d[i].x=1e9, d[i].y=b[i];
	
	Q.push({1, b[1],0}); rs=1e9; d[1].y=b[1];
	while (!Q.empty()) {
		int x=Q.front().x;
		int c=Q.front().c;
		int g=Q.front().g; Q.pop(); 
		g=max(g,b[x]);
		
	
		if (x==n) {
			rs=min(rs,c); continue;
		}
		for (int i=0; i<V[x].size(); i++) {
			if (V[x][i].y>g) continue;
			int y=V[x][i].x;
			int cy=V[x][i].y;
			
			if (d[y].x>cy+c) {
				d[y].y=max(d[y].y, d[x].y);
				d[y].x=cy+c;
				Q.push({y,d[y].y,d[y].x});
			} else if (d[y].y<g) {
				d[y].y=g; 
				Q.push({y,g,cy+c});
			}
		}
	}
	
	cout<<rs;
	return 0;
}