Cod sursă (job #677298)

#include <bits/stdc++.h>
#define N 805
#define pb push_back
#define INF 0x3f3f3f3f

using namespace std;

ifstream fin("dragoni2.in");
ofstream fout("dragoni2.out");

int task, n, m, M, Min = INF, aux;
bool C[N];
int D[N][N];
int v[N];
vector<pair<int, int>>a[N];
queue <pair<int, int> > Q;
void citire() {
    int x, y, z;
    fin >> task >> n >> m;
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }
    for (int i = 1; i <= m; ++i) {
        fin >> x >> y >> z;
        a[x].pb({ z,y });
        a[y].pb({ z,x });
    }
}
void dfs(int nod) {
    C[nod] = 1;
    for (auto i : a[nod])
        if (!C[i.second] && i.first <= v[1]) {
            if (v[i.second] > M)
                M = v[i.second];
            dfs(i.second);
        }
}
void dijkstra(int nod) {
    D[1][1] = 0;
    Q.push({ 1,1 });
    while (!Q.empty()) {
        int elem = Q.front().first, tip_dragon = Q.front().second;
        Q.pop();
        for (auto i : a[elem]) {
            if (i.first <= v[tip_dragon]) {
                if (v[tip_dragon] > v[i.second])
                    aux = tip_dragon;
                else
                    aux = i.second;
                if (D[i.second][aux] > D[elem][tip_dragon] + i.first) {
                    D[i.second][aux] = D[elem][tip_dragon] + i.first;
                    Q.push({ i.second,aux });
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
        if (D[n][i] < Min)
            Min = D[n][i];
    fout << Min;
}
void solve() {
    dfs(1);
    if (task == 1) {
        fout << M;
        return;
    }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            D[i][j] = INF;
    dijkstra(1);
}
int main() {
    citire();
    solve();
    return 0;
}