Cod sursă (job #692302)

#include <fstream>
#include <stdio.h>
#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();
    }
}
FILE* file_=fopen("dragoni2.in","r");
char buff[10000];
int poz;
void citeste(int &numar)
{
    numar=0;
    while(buff[poz]<'0' || buff[poz]>'9')
    {
        if(++poz==10000)
            fread(buff,1,10000,file_),poz=0;
    }
    while(buff[poz]>='0' && buff[poz]<='9')
    {
        numar=numar*10+buff[poz]-'0';
        if(++poz==10000)
            fread(buff,1,10000,file_),poz=0;
    }
}
int main()
{
    citeste(p);
    citeste(n);
    citeste(m);
    //fin >> p >> n >> m;
    for(int i=1;i<=n;i++)
    {
        citeste(val[i]);
        //fin >> val[i];
    }

    for(int i=1;i<=m;i++)
    {
        int a,b,c;
        citeste(a);
        citeste(b);
        citeste(c);
        //fin >> a >> b >> c;
        if(A[a][b]==0)
        {
            G[a].push_back(b);
            G[b].push_back(a);
        }
        if(a!=b && (A[a][b]==0 || A[a][b]>c)) A[a][b]=A[b][a]=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;
}