Cod sursă (job #334632)

#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dragoni2.in");
ofstream fout("dragoni2.out");
const short Nmax = 1005;
const int inf = LONG_MAX;
int op , n , m , D[Nmax] , dp[Nmax][Nmax] , mxop1,minop2;
vector< pair < int , int > > L[Nmax];
queue < pair < int , int > > Q;
bool viz[Nmax] , ad[Nmax][Nmax];
inline void Read()
{
    fin >> op;
    fin >> n >> m;
    for(int i = 1 ; i <= n ; i++)
        fin >> D[i];
    for(int i = 1 ; i <= m ; i++)
    {
        int d , x , y;
        fin >> x >> y >> d;
        L[x] . push_back ({y , d});
        L[y] . push_back ({x , d});
    }
}
inline void DFS(int varf)
{
    viz[varf] = true;
    for(auto w : L[varf])
        if(!viz[w . first] && w . second <= D[1])
        {
            mxop1 = max(mxop1 , D[w . first]);
            DFS(w . first);
        }
}
inline void OP2_DP()
{
    Q .push({1 , 1});
    for(int i = 1 ; i <= n; i++)
        for(int j = 1 ; j <= m ; j++)
            dp[i][j] = inf;
    dp[1][1] = 0;
    ad[1][1] = true;
    int x , k;
    while(!Q . empty())
    {
        x = Q . front() . first;
        k = Q . front() . second;
        ad[x][k] = false;
        Q . pop();
        for(auto w : L[x])
            if(D[k] >= w . second)
        {
            int newd;
            if(D[k] < D[w . first])
                newd = w . first;
            else newd = k;
            if(dp[w . first][newd] >= dp[x][k] + w . second)
            {
                dp[w . first][newd] = dp[x][k] + w . second;
                if(!ad[w . first][newd])
                {
                    Q . push({w . first , newd});
                    ad[w . first][newd] = true;
                }
            }
        }
    }
    minop2 = dp[n][1];
    for(int i = 2 ; i <= n ; i++)
        minop2 = min(minop2 , dp[n][i]);
    fout << minop2 << "\n";
}
int main()
{
    Read();
    if(op == 1)
    {
        DFS(1);
        fout << mxop1 << "\n";
    }
    else
        OP2_DP();
    fin.close();
    fout.close();
    return 0;
}