Cod sursa(job #3213996)

Utilizator ana_valeriaAna Valeria Duguleanu ana_valeria Data 13 martie 2024 17:45:20
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <fstream>
#include <vector>
#include <set>
#define MAX 50000
#define INF 2000000000
using namespace std;
ifstream cin ("dijkstra.in");
ofstream cout ("dijkstra.out");
int dist[MAX + 10];
vector <pair <int, int>> graph[MAX + 10];
set <pair <int, int>> s;
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        graph[x].push_back({c, y});
    }
    for (int i = 2; i <= n; i++)
        dist[i] = INF;
    s.insert({0, 1});
    while (!s.empty())
    {
        int node = s.begin()->second;
        s.erase(s.begin());
        for (const auto &it : graph[node])
        {
            int cost = it.first;
            int next = it.second;
            if (dist[next] > dist[node] + cost)
            {
                if (dist[next] != INF)
                    s.erase({dist[next], next});
                dist[next] = dist[node] + cost;
                s.insert({dist[next], next});
            }
        }
    }
    for (int i = 2; i <= n; i++)
        if (dist[i] == INF)
            cout << "0 ";
        else
            cout << dist[i] << ' ';
    return 0;
}