Cod sursa(job #2738643)

Utilizator andreiomd1Onut Andrei andreiomd1 Data 6 aprilie 2021 10:20:23
Problema Algoritmul lui Dijkstra Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef pair < int, int > Edge;

const int NMAX = 5e4 + 1;
const int INF = 1e9;

int N, M;

vector < Edge > G[NMAX];

int d[NMAX];
bool Sel[NMAX];

static inline void Read ()
{
    f.tie(nullptr);

    f >> N >> M;

    for(int i = 1; i <= M; ++i)
    {
        int X = 0, Y = 0, C = 0;
        f >> X >> Y >> C;

        G[X].push_back({C, Y});
    }

    return;
}

static inline void Dijkstra (int S)
{
    for(int i = 1; i <= N; ++i)
        d[i] = INF, Sel[i] = 0;

    d[S] = 0, Sel[S] = 1;

    for(auto it : G[S])
        if(it.first < d[it.second])
            d[it.second] = it.first;

    for(int i = 2; i <= N; ++i)
    {
        int Node = 0, Cost = INF;

        for(int j = 1; j <= N; ++j)
            if(!Sel[j] && d[j] < Cost)
                Cost = d[j], Node = j;

        if(Node == 0)
            return;

        Sel[Node] = 1;

        for(auto it : G[Node])
            if(Cost + it.first < d[it.second])
                d[it.second] = Cost + it.first;
    }

    return;
}

static inline void Solve ()
{
    Dijkstra(1);

    for(int i = 2; i <= N; ++i)
    {
        g << ((d[i] != INF) ? d[i] : 0);

        if(i != N)
            g << ' ';
    }

    g << '\n';

    return;
}

int main()
{
    Read();

    Solve();

    return 0;
}