Cod sursa(job #1502210)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 14 octombrie 2015 12:47:51
Problema Algoritmul lui Dijkstra Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <set>

using namespace std;

#define nmax 50001
#define mmax 250001
#define inf 1000000005

int n, m;
int Cost[nmax];
vector < pair <int, int> > G[nmax];
set < pair <int, int> > S;

ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");

void read()
{
    int a, b, c;
    fi >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        // nodul 1, nodul 2, cost
        fi >> a >> b >> c;
        G[a].push_back(make_pair(b, c));
    }
}

void init()
{
    // nodul curent, costul de la nodul 1 pana la nodul curent
    S.insert(make_pair(1, 0));
    for (int i = 2; i <= n; i++)
        Cost[i] = inf;
}

void dijkstra()
{

    while (!S.empty())
    {

        int nodulCurent = (*S.begin()).first;
        int costulCurent = (*S.begin()).second;

        S.erase(S.begin());

        for (int i = 0; i < G[nodulCurent].size(); i++)
        {
            int vecin = G[nodulCurent][i].first;
            int costulVecin = G[nodulCurent][i].second;

            if (costulVecin + costulCurent < Cost[vecin])
            {
                Cost[vecin] = costulVecin + costulCurent;
                S.insert(make_pair(vecin, Cost[vecin]));
            }

        }

    }

}

void write()
{
    for (int i = 2; i <= n; i++)
    {
        if (Cost[i] == inf)
            Cost[i] = 0;
        fo << Cost[i] << " ";
    }
    fo << "\n";
}

int main()
{

    read();

    init();

    dijkstra();

    write();

    return 0;
}