Cod sursa(job #2638864)

Utilizator llama27Asd asd llama27 Data 30 iulie 2020 12:37:42
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.75 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <queue>
#include <cmath>
#include <string>
#include <set>
using namespace std;

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

// DIJSKTRA with MIN-HEAP using PRIORITY QUEUE
const int NMAX = 50005;

int n, m;
float dist[NMAX];
vector<pair<int, int>> g[NMAX];//  g[index], edge = [index,g[index].first] 
                               //  cost = g[index].second

auto comparator = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second; };

void read()
{
    in >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int x, y, c;
        in >> x >> y >> c;
        g[x].push_back({ y,c });
    }
    for (int i = 0; i <= n; i++)
        dist[i] = INFINITY;
}

void dijsktra(int startNode)
{
    priority_queue < pair<int, int>, vector<pair<int, int>>, decltype(comparator)> pq(comparator);

    pq.push({ startNode,0 }); // node, cost
    dist[startNode] = 0;

    while (!pq.empty())
    {
        int node = pq.top().first,
            cost = pq.top().second;

        pq.pop();

        
        if(dist[node] == cost)
            for (auto const& it : g[node])
            {
                int nextNode = it.first,
                    nextCost = it.second;
                if (dist[node] + nextCost < dist[nextNode])
                {
                    dist[nextNode] = dist[node] + nextCost;
                    pq.push({ nextNode,dist[nextNode] });
                }
            }
    }
}

void print()
{
    for (int i = 2; i <= n; i++)
        out << (dist[i] == INFINITY ? 0 : dist[i]) << ' ';
}

int main()
{
    read();
    dijsktra(1);
    print();
}