Cod sursă (job #677292)

#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;
bool C[N];
int D[N][N];
int v[N];
vector<pair<int, int>>a[N];
struct cmp {
    inline bool operator()(pair<int, int> a, pair<int, int> b) {

        return D[a.first][a.second] > D[b.first][b.second];
    }
};
priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> 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({ y,z });
        a[y].pb({ x,z });
    }
}
void dfs(int nod) {
    C[nod] = 1;
    for (auto i : a[nod])
        if (!C[i.first] && i.second <= v[1]) {
            if (v[i.first] > M)
                M = v[i.first];
            dfs(i.first);
        }
}
void dijkstra(int nod) {
    D[1][1] = 0;
    Q.push({ 1,1 });
    while (!Q.empty()) {
        int elem = Q.top().first, tip_dragon = Q.top().second;
        Q.pop();
        int dist1 = D[elem][tip_dragon];
        if (v[tip_dragon] < v[elem])
            tip_dragon = elem;
        for (int i = 0; i < a[elem].size(); ++i) {
            int vecin = a[elem][i].first, distanta = a[elem][i].second;
            if (distanta <= v[tip_dragon] && dist1 + distanta <= D[vecin][tip_dragon]) {
                D[vecin][tip_dragon] = dist1 + distanta;
                Q.push({ vecin,tip_dragon });
            }
        }
    }
    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() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    citire();
    solve();
    return 0;
}