Cod sursă (job #803212)

#include <iostream>
#include <fstream>
#include <queue>
#include <tuple>
#include <vector>

using namespace std;
ifstream fin("lanterna.in");
ofstream fout("lanterna.out");


const int MAXN=50,MAXW=1000;
int n,i,j,m,k,sol[MAXW+5],cost,timp,d[MAXN+5];
bool rechargable[MAXN+5];
vector <tuple<int,int,int>> muchii[MAXN+5];
priority_queue <tuple<int,int,int> , vector<tuple<int,int,int>>, greater<tuple<int,int,int>>> pq;
bool valorimuchii=1;

void read()
{
   fin>>n>>k;
   for (i=1; i<=n; i++)
        fin>>rechargable[i];

   fin>>m;
   while (m)
   {
       fin>>i>>j>>timp>>cost;

       if (cost>0)
        valorimuchii=0;

       muchii[i].push_back({j,timp,cost});
       muchii[j].push_back({i,timp,cost});
       m--;
   }
}

void mintime()
{
    int mn=1e9;
    for (i=1; i<=k; i++)
        mn=min(mn,sol[i]);



    if (valorimuchii)
        fout<<mn<<" "<<0;
    else
    for (i=1; i<=k; i++)
    {
        if (mn==sol[i])
        {
            fout<<sol[i]<<" "<<i;
            break;
        }
    }
}

void init()
{
    for (i=1; i<=k; i++)
        sol[i]=1e9;
}

void initdijkstra(int w)
{
    for (i=1; i<=n; i++)
        d[i]=-1e9;

    d[1]=w;

    while (!pq.empty())
        pq.pop();
}

void solve()
{
    for (int w=1; w<=k; w++)
    {
        initdijkstra(w);

        pq.push({0,1,w});
        while (!pq.empty())
        {
            int timp=get<0>(pq.top()), nod=get<1>(pq.top()),energie=get<2>(pq.top());
            pq.pop();

            if (nod==n)
            {
                sol[w]=timp;
                break;
            }

            if (rechargable[nod])
                energie=w;

            d[nod]=max(d[nod],energie);

            for (auto x: muchii[nod])
            {
                int nod2=get<0>(x),timpmuchie=get<1>(x),costmuchie=get<2>(x);

                if (energie>=costmuchie && energie-costmuchie>d[nod2])
                    pq.push({timp+timpmuchie,nod2,energie-costmuchie});
            }

        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    fin.tie(0); fout.tie(0);

    read();
    init();
    solve();
    mintime();
    return 0;
}