Cod sursa(job #1277347)

Utilizator mvcl3Marian Iacob mvcl3 Data 27 noiembrie 2014 16:12:57
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 kb
#include <cstdio>
#include <set>
#include <vector>

#define Max_Size 250009
#define Max_K 1001
#define Max_Buf 32
#define isnumber(z) ('0' <= (z) && (z) <= '9')

using namespace std;

typedef pair < int , int > POINT;

const char iname[] = "pscnv.in";
const char oname[] = "pscnv.out";

int N, M, S, F, D[Max_Size];

vector < POINT > V[Max_Size];
set < POINT > my_Heap;

inline void Read_Data()
{
    FILE *in = fopen(iname, "r");

    fscanf(in, "%d%d%d%d", &N, &M, &S, &F);

    char buffer[Max_Buf];

    fgets(buffer, Max_Buf, in);

    for(int j, x, y, p, i = 1; i <= M; ++i)    {
        x = y = p = 0;

        fgets(buffer, Max_Buf, in);

        for(j = 0; isnumber(buffer[j]); x = x * 10 + (buffer[j] - '0'), ++j);
        for(j = j + 1; isnumber(buffer[j]); y = y * 10 + (buffer[j] - '0'), ++j);
        for(j = j + 1; isnumber(buffer[j]); p = p * 10 + (buffer[j] - '0'), ++j);

        V[x].push_back( {y, p} );
    }
}

inline void Init()
{
    for(int i = 1; i <= N; ++i) D[i] = Max_K;
}

void Djikstra()
{
    D[S] = 0;
    my_Heap.insert( {0, S} );

    vector < POINT > :: iterator it;

    while(!my_Heap.empty()) {
        POINT nod = *my_Heap.begin();
        my_Heap.erase(nod);

        for(it = V[nod.second].begin(); it != V[nod.second].end(); ++it)       {
            if(D[it->first] > max( nod.first, it->second) )  {
                my_Heap.erase( {D[it->first], it->first});

                D[it->first] = max(nod.first , it->second );

                my_Heap.insert( { D[it->first], it->first} );
            }
        }
    }
}

int main()
{
    Read_Data();
    Init();
    Djikstra();

    FILE *out = fopen(oname,"w");
    fprintf(out, "%d\n", D[F]);

    return 0;
}