Cod sursă (job #692244)

#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

ifstream cin("dragoni2.in");
ofstream cout("dragoni2.out");

int cerinta, n, m, a, b, distanta;
vector<vector<int>> lista(800 + 10);
vector<int> d(800 + 10), dragoni(800 + 10);
vector<vector<pair<int, int>>> lista2(800 + 10);
vector<vector<int>> matrice(800 + 10, vector<int>(800 + 10));
bool vizitat[800 + 10], vizitate[800 + 10][800 + 10];

void citire()
{
	cin >> cerinta >> n >> m;
	for (int i = 1; i <= n; i++)
		cin >> d[i];
}


int main()
{
	citire();
	if (cerinta == 1)
	{
		for (int i = 1; i <= m; i++)
		{
			cin >> a >> b >> distanta;
			//Daca dragonul de pe insula 1 poate parcurge aceasta muchie
			if (d[1] >= distanta)
			{
				lista[a].push_back(b);
				lista[b].push_back(a);
			}
		}
		queue<int> coada;
		vizitat[1] = true;
		coada.push(1);
		while (coada.empty() == false)
		{
			int nod = coada.front();
			coada.pop();
			for(auto i : lista[nod])
				if(vizitat[i] == false)
				{
					vizitat[i] = true;
					coada.push(i);
				}
		}
		int rezultat = d[1];
		for (int i = 1; i <= n; i++)
			if (vizitat[i] == true && d[i] > rezultat)
				rezultat = d[i];
		cout << rezultat;
	}
	else
	{
		for (int i = 1; i <= m; i++)
		{
			cin >> a >> b >> distanta;
			lista2[a].push_back({ distanta, b });
			lista2[b].push_back({ distanta ,a });
		}
		//Sortare
		for (int i = 1; i <= n; i++)
			sort(lista2[i].begin(), lista2[i].end());
		//Initializare
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				matrice[i][j] = 1000000000;
		int rezultat = 1000000000;
		//Bellman-Ford
		queue<pair<int, int>> coada;
		coada.push({ 1, 1 });
		vizitate[1][1] = true;
		matrice[1][1] = 0;
		while (coada.empty() == false)
		{
			int insula = coada.front().first;
			int insulaDragon = coada.front().second;
			vizitate[insula][insulaDragon] = false;
			//Distanta care a fost parcursa pana in acest moment
			int distanta = matrice[insula][insulaDragon];
			coada.pop();
			//Daca avem un dragon mai mare atunci se alege acest dragon
			if (d[insula] > d[insulaDragon])
				insulaDragon = insula;
			for(auto i : lista2[insula])
				if (d[insulaDragon] >= i.first)
				{
					//Daca acest drum nu este optim atunci se ignora
					if (distanta + i.first >= rezultat || distanta + i.first >= matrice[i.second][insulaDragon])
						continue;
					//Daca nodul vecin este chiar nodul n atunci se actualizeaza rezultatul
					if (i.second == n)
					{
						rezultat = distanta + i.first;
						continue;
					}
					matrice[i.second][insulaDragon] = distanta + i.first;
					if (vizitate[i.second][insulaDragon] == false)
					{
						vizitate[i.second][insulaDragon] = true;
						coada.push({ i.second, insulaDragon });
					}
				}
		}
		cout << rezultat;
	}
	return 0;
}