Cod sursă (job #692166)

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

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

int cerinta, n, m, a, b, cost, dragonMaxim;
vector<int> d(800 + 10), dragoni(800 + 10, 0), costuri(800 + 10, 1000000000);
vector<vector<int>> matrice(800 + 10, vector<int>(800 + 10));
bool vizitat[800 + 10];

void citire()
{
	cin >> cerinta >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			matrice[i][j] = 0;
	for (int i = 1; i <= n; i++)
		cin >> d[i];
	for (int i = 1; i <= m; i++)
	{
		cin >> a >> b >> cost;
		matrice[a][b] = matrice[b][a] = cost;
	}
}

void DFS1(int nod, int dragon)
{
	vizitat[nod] = true;
	for(int i = 1;i <= n;i++)
		if (matrice[nod][i] != 0 && vizitat[i] == false && dragon >= matrice[nod][i])
		{
			if (d[i] > dragonMaxim)
				dragonMaxim = d[i];
			DFS1(i, dragon);
		}

}

void Dijkstra()
{
	queue<int> coada;
	coada.push(1);
	dragoni[1] = d[1];
	costuri[1] = 0;
	while (coada.empty() == false)
	{
		int nod = coada.front();
		coada.pop();
		for(int i = 1;i <= n;i++)
			if (matrice[nod][i] != 0 && vizitat[i] == false && dragoni[nod] >= matrice[nod][i])
			{
				vizitat[i] = true;
				dragoni[i] = max(dragoni[nod], d[i]);
				if (dragoni[i] > dragoni[nod])
					coada.push(i);
				costuri[i] = costuri[nod] + matrice[nod][i];
				coada.push(i);
			}
			else if (matrice[nod][i] != 0 && dragoni[nod] >= matrice[nod][i] && (costuri[nod] + matrice[nod][i] < costuri[i]))
			{
				dragoni[i] = max(dragoni[nod], d[i]);
				if (dragoni[i] > dragoni[nod])
					coada.push(i);
				costuri[i] = costuri[nod] + matrice[nod][i];
				coada.push(i);
			}
	}
}

int main()
{
	citire();
	if (cerinta == 1)
	{
		DFS1(1, d[1]);
		cout << dragonMaxim;
	}
	else
	{
		Dijkstra();
		cout << costuri[4];
	}
	return 0;
}