Cod sursă (job #677333)

#include <bits/stdc++.h>
using namespace std;

#define pb push_back

const string fn = "dragoni2";
ifstream fin(fn + ".in");
ofstream fout(fn + ".out");

const int mod = 100003;

int n, m, task;
int dp[2005][2005];

int ans;
int d[805];

bitset<805> viz;
vector<pair<int, int>> g[805];
queue<pair<int, int>> q;

void dfs(int nod)
{
    viz[nod] = 1;
    ans = max(ans, d[nod]);
    for (auto i : g[nod])
        if (!viz[i.second] && i.first <= d[1])
            dfs(i.second);
}

int main()
{

    ios_base::sync_with_stdio(false);
    cin.tie();

    fin >> task >> n >> m;
    for (int i = 1; i <= n; ++i)
        fin >> d[i];
    while (m--)
    {
        int x, y, w;
        fin >> x >> y >> w;
        g[x].pb({w, y});
        g[y].pb({w, x});
    }
    if (task == 1)
    {
        dfs(1);
        fout << ans << '\n';
    }
    else
    {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                dp[i][j] = 2e9;
        q.push({1, 1});
        dp[1][1] = 0;
        while (!q.empty())
        {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (auto i : g[x])
                if (i.first <= d[y])
                {
                    int _ = 0;
                    if (d[y] > d[i.second])
                        _ = y;
                    else
                        _ = i.second;
                    if (dp[i.second][_] > dp[x][y] + i.first)
                    {
                        dp[i.second][_] = dp[x][y] + i.first;
                        q.push({i.second, _});
                    }
                }
        }
        ans = 2e9;
        for (int i = 1; i <= n; ++i)
            ans = min(ans, dp[n][i]);
        fout << ans << '\n';
    }
    return 0;
}