Cod sursă (job #691678)

#include <fstream>
#include <vector>
#include <map>
#include <unordered_map>
using namespace std;
ifstream fin("dragoni2.in");
ofstream fout("dragoni2.out");
long long n, m, i, j, p, d[801], a, ii, b, c, viz[801], viz2[801][801];
vector <unordered_map <long long, long long> > g;
void dfs1 (long long s)
{
    viz[s] = 1;
    for (auto it : g[s])
    {
        long long t = it.first;
        if (viz[t] == 0)
            dfs1(t);
    }
}
int main()
{
    fin.tie(0);
    fin.sync_with_stdio(false);
    fout.sync_with_stdio(false);
    fin >> p >> n >> m; g.resize(n+1);
    for (i = 1; i <= n; i++)
        fin >> d[i];
    for (i = 1; i <= m; i++)
    {
        fin >> a >> b >> c;
        if ((p == 1 && c <= d[1]) || p == 2)
        {
            if (g[a].find(b) == g[a].end() ||  (g[a].find(b) != g[a].end() && g[a][b] > c))g[a][b] = c;
            if (g[b].find(a) == g[b].end() ||  (g[b].find(a) != g[b].end() && g[b][a] > c))g[b][a] = c;
        }
    }
    if (p == 1)
    {
        dfs1(1);
        long long mx = 0;
        for (i = 1; i <= n; i++)
            if (viz[i] == 1)
                mx = max (mx, d[i]);
        fout << mx;
    }
    if (p == 2)
    {
        unordered_multimap <long long, pair <long long, long long> > m;
        for (i = 2; i <= n; i++)
            viz[i] = 2e9;
        viz[1] = 0;
        for (int h = 1; h <= n; h++) viz2[h][h] = 1;
        m.insert({0, {1, 1}});
        while (!m.empty())
        {
            long long c  = (*m.begin()).first;
            long long is = (*m.begin()).second.first;
            long long dr = (*m.begin()).second.second;
            m.erase(m.begin());
            for (auto it : g[is])
            {
                long long t = it.first, k = it.second;
                if (d[dr] >= k && viz2[t][dr] == 0)
                {
                    if (viz[t] > c+k) viz[t] = c+k;
                    viz2[t][dr] = 1;
                    int r = dr;
                    if (d[t] > d[dr]) r = t;
                    if (t != n) m.insert({c+k, {t, r}});
                }
            }
        }
        fout << viz[n];
    }
    return 0;
}