Cod sursă (job #692278)

#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];
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();
    }
}
void bfs2(int x)
{
    q2.push(make_pair(x,x));
    while(!q2.empty())
    {
        int xc=q2.front().first;
        int type=q2.front().second;
        for(int i=1;i<=n;i++)
        {
            if(A[i][xc]<=val[type] && A[i][xc]!=0 && 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();
    }
}
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<=n;i++)
    {
        for(int j=1;j<=n;j++)
            viz2[i][j]=maxint;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        fin >> a >> b >> c;
        if(a!=b && (A[a][b]==0 || A[a][b]>c)) A[a][b]=A[b][a]=c;
    }
    if(p==1)
    {
        bfs(1);
        fout << dmax;
    }
    else
    {
        viz2[1][1]=0;
        bfs2(1);
        int minim=maxint;
        for(int i=1;i<=n;i++)
            minim=min(minim,viz2[n][i]);
        fout << minim;
    }
    return 0;
}