Cod sursă (job #692290)

#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dragoni2.in");
ofstream fout("dragoni2.out");
const int maxint=1000000001;
int p,n,m,val[801],A[801][801],viz[801],dmax,viz2[801][801],minim=1000000001;
vector<int> G[801];
queue<int> q;
queue<pair<int,int>> q2;
void bfs(int x)
{
    dmax=val[x];
    viz[x]=1;
    q.push(x);
    while(!q.empty())
    {
        int xc=q.front();
        dmax=max(dmax,val[xc]);
        for(int i=1;i<=n;i++)
        {
            if(A[i][xc]<=val[x] && A[i][xc]!=0 && viz[i]==0)
            {
                viz[i]=viz[xc]+1;
                q.push(i);
            }
        }
        q.pop();
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    fin.tie(0);
    fin >> p >> n >> m;
    for(int i=1;i<=n;i++)
    {
        fin >> val[i];
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin >> a >> b >> c;
        if(A[a][b]==0)
        {
            G[a].push_back(b);
            G[b].push_back(a);
            A[a][b]=A[b][a]=min(A[a][b],c);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            viz2[i][j]=maxint;
            if(A[i][j]==0) A[i][j]=maxint;
        }
    }
    if(p==1)
    {
        bfs(1);
        fout << dmax;
    }
    else
    {
        viz2[1][1]=0;
        q2.push(make_pair(1,1));
        while(!q2.empty())
        {
            int xc=q2.front().first;
            int type=q2.front().second;
            if(xc==n) minim=min(minim,viz2[xc][type]);
            for(vector<int>::iterator it=G[xc].begin();it!=G[xc].end();++it)
            {
                int i=(*it);
                if(A[i][xc]<=val[type] && viz2[xc][type]+A[i][xc]<viz2[i][type])
                {
                    viz2[i][type]=viz2[xc][type]+A[i][xc];
                    viz2[i][i]=min(viz2[i][type],viz2[i][i]);
                    if(val[type]>=val[i]) q2.push(make_pair(i,type));
                    else q2.push(make_pair(i,i));
                }
            }
            q2.pop();
        }
        fout << minim;
    }
    return 0;
}