Cod sursa(job #2492253)

Utilizator RadianElevenAdrian Ariotn RadianEleven Data 14 noiembrie 2019 11:21:46
Problema PScNv Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.76 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;
ifstream f ("pscnv.in");
ofstream g ("pscnv.out");
int cost[500001];
int pct, edges;
queue<int> coada;
vector< pair <int, int> > muchii[500002];
struct Nod{
    int nod;
    int val;
};
Nod heap[500004];
int n;
Nod getMin()
{
    return heap[1];
}
void add(Nod x)
{

    n++;
    int poz=n;
    heap[n]=x;
    while(poz>1 && heap[poz/2].val>heap[poz].val)
    {
        swap(heap[poz/2], heap[poz]);
        poz/=2;
    }
}
int popMin()
{

    heap[1]=heap[n];
    heap[n]={0,0};
    int poz=1;
    n--;
    while(2*poz<=n)
    {
        poz*=2;
        if(poz<n && heap[poz].val>heap[poz+1].val) poz++;
        if(heap[poz].val < heap[poz/2].val)
            swap(heap[poz/2], heap[poz]);
        else poz=n;
    }
}


int main()
{
    int xnod, ynod;
    f>>pct>>edges>>xnod>>ynod;
    for(int i=1;i<=edges;++i)
    {
        int c,b,a;
        f>>a>>b>>c;
        muchii[a].push_back(make_pair(b,c));

    }
     for(int i=1;i<=pct;++i)
       cost[i]=1e9;
    Nod nod={xnod,0};
    cost[xnod]=0;
    add({xnod,0});

    Nod cop;
    while(n>0)
    {
        nod=getMin();
        popMin();
        if(nod.val<=cost[nod.nod])
        {

            for(int i=0; i<muchii[nod.nod].size(); ++i)
            {
                pair<int, int> copil=muchii[nod.nod].at(i);

                cop.nod=copil.first;
                cop.val=copil.second;
                if(cost[nod.nod]<cost[cop.nod] && cop.val < cost[ynod])
                {
                    cost[cop.nod] = max(cop.val, cost[nod.nod]);
                }
                add(cop);
            }
        }
    }
    g<<cost[ynod];


    return 0;
}