Cod sursă (job #446076)

#include <bits/stdc++.h>
#define DMAX 1000
#define INFINIT 1000000000
using namespace std;
ifstream fin("lanterna.in");
ofstream fout("lanterna.out");
void reset();
struct traseu{int timp,curent;}cost[DMAX];
struct ele{int y,time,wat;};
 
inline bool operator<(ele x, ele y) {
    return x.wat > y.wat;
}
priority_queue<ele> Heap;
void dijkstra(int energie);
void citire();
vector<ele> a[DMAX];
int n,m,k;
bool baza[DMAX];
int tmin,emin;
int main()
{int st,dr,mij,i;
    citire();
 
    dijkstra(k);
    tmin=cost[n].timp;
    cout<<tmin;
    emin=k;
    st=0;
    dr=k;
 
    while(st<dr-1)
    {
        mij=(st+dr)/2;
        dijkstra(mij);
        if(cost[n].timp==tmin)
            emin=mij,dr=mij;
        else
            st=mij;
 
    }
    fout<<tmin<<' '<<emin;
}
 
void citire()
{int i,x,y,timp,wat;
    fin>>n>>k;
    for(i=1;i<=n;i++)
        fin>>baza[i];
    fin>>m;
 
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>timp>>wat;
        a[x].push_back({y,timp,wat});
        a[y].push_back({x,timp,wat});
 
    }
}
void dijkstra(int energie)
{int i,val,now,start;
ele x;
int varf,capat,timpi,eon;
 
    start=1;
    for(i=1;i<=n;i++)
        cost[i].timp=INFINIT;
         for(i=1;i<=n;i++)
        cost[i].curent=INFINIT;
    Heap.push({1,0,0});
    //pred[1].cine=0;
 
    while(Heap.size())
    {
        x=Heap.top();
         //fout<<Heap.size()<<' '<<"ele"<<x<<' ';
 
        Heap.pop();
        varf=x.y;
          //fout<<x<<'\n';
            for(i=0;i<a[varf].size();i++)
            {
                capat=a[varf][i].y;
                timpi=x.time+a[varf][i].time;
                if(baza[varf])
                    eon=a[varf][i].wat;
                else
                    eon=a[varf][i].wat+x.wat;
                if(eon<=energie)
                {
                    if(timpi<cost[capat].timp||eon<cost[capat].curent)
                    {
                        cost[capat].timp=timpi;
                        if(eon<cost[capat].curent)
                            cost[capat].curent=eon;
                        Heap.push({capat,cost[capat].timp,eon});
                    }
 
                }
        /*for(i=1;i<=n;i++)
            fout<<cost[i].timp<<' ';
        fout<<'\n';*/
 
        }
        }