Cod sursă (job #692301)

#include <bits/stdc++.h>

using namespace std;

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

int p, n, m, a, b, c;
int D[805];
long long Dist[805][805];
bitset<805> incoada[805];
vector<pair<int, int>> G[805];

int bfs1()
{
    bool vis[805];
    queue<int> Q;
    Q.push(1);
    vis[1] = 1;
    int maxx = D[1];

    while ( !Q.empty() )
    {
        int x = Q.front();
        Q.pop();

        for ( auto a : G[x] )
            if ( D[1] >= a.second && !vis[a.first] )
            {
                vis[a.first] = 1;
                maxx = max(maxx, D[a.first]);
                Q.push(a.first);
            }
    }
    return maxx;
}

int main()
{
    fin >> p >> n >> m;

    for ( int i = 1; i <= n; i++ )
        fin >> D[i];

    for ( int i = 1; i <= m; i++ )
    {
        fin >> a >> b >> c;
        G[a].push_back({ b, c });
        G[b].push_back({ a, c });
    }

    if ( p == 1 )
    {
        fout << bfs1();
        return 0;
    }

    for ( int i = 1;i <= n;i++ )
        for ( int j = 1;j <= n;j++ )
            Dist[i][j] = (1ll << 60);

    queue<pair<int, int>> Q; // {a, b} - pe insula a cu dragonul b
    Q.push({ 1, 1 });
    incoada[1][1] = 1;
    Dist[1][1] = 0;
    long long len = (1ll << 60);

    while ( !Q.empty() )
    {
        int ix = Q.front().first, dx = Q.front().second;
        Q.pop();
        incoada[1][1] = 0;
        long long dist = Dist[ix][dx];

        if ( D[ix] > D[dx] ) dx = ix;
        for ( auto ppp : G[ix] )
        {
            int ivec = ppp.first, distvec = ppp.second;

            if ( D[dx] < distvec )continue;
            if ( dist + distvec >= len || dist + distvec >= Dist[ivec][dx] )continue;

            if ( ivec == n )
            {
                len = dist + distvec;
                continue;
            }

            Dist[ivec][dx] = dist + distvec;

            if ( !incoada[ivec][dx] )
            {
                incoada[ivec][dx] = 1;
                Q.push({ ivec, dx });
            }
        }
    }

    fout << len;
}