Cod sursă (job #677273)

#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
 
ifstream fin("dragoni2.in");
ofstream fout("dragoni2.out");
 
int cer, n, m, d[805], sol;
vector <pair<int, int > > a[805];
bitset <805> viz;
int dp[805][805];
queue <pair<int, int> > Q;
void Dfs(int x)
{
    viz[x] = 1;
    sol = max(sol, d[x]);
    for (auto w : a[x])
        if (viz[w.second] == 0 and w.first <= d[1])
             Dfs(w.second);   
}
 
void Test_Case()
{
    int i, j, x, y, c, urm;
    fin >> cer >> n >> m;
    for (i = 1; i <= n; i++)
        fin >> d[i];
 
    for (i = 1; i <= m; i++)
    {
        fin >> x >> y >> c;
        a[x].push_back({ c, y });
        a[y].push_back({ c, x });
    }
 
    if (cer == 1)
    {
        Dfs(1);
        fout << sol << "\n";
    }
    else
    {
        for (i = 1; i <= n; i++)
            for (j = 1; j <= n; j++)
                dp[i][j] = INF;
 
        Q.push({ 1, 1 });
        dp[1][1] = 0;
        while (!Q.empty())
        {
            x = Q.front().first;
            y = Q.front().second;
            Q.pop();
            for (auto w : a[x])
            if (w.first <= d[y])
            {
                urm = (d[y] > d[w.second]) ? y : w.second;
                if (dp[w.second][urm] > dp[x][y] + w.first)
                {
                    dp[w.second][urm] = dp[x][y] + w.first;
                    Q.push({ w.second, urm });
                }
            }
        }
        sol = INF;
        for (i = 1; i <= n; i++)
            sol = min(sol, dp[n][i]);
        fout << sol << "\n";
 
    }
 
}
 
int main()
{
    int t;
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    t = 1;
    while (t--)
        Test_Case();
 
    return 0;
}