Cod sursa(job #3374817)

Utilizator calin06calin mihaescu calin06 Data 9 noiembrie 2026 14:26:47
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;


const int nmax = 250010;
const int inf = INT_MAX;

int n,m;
vector<vector<pair<int,int>>>graf(nmax);

void dijkstra(int nod_start,vector<vector<pair<int,int>>>&graf,vector<bool>&viz,vector<int>&dist)
{
    priority_queue<pair<int,int>>pq;
    dist[nod_start] = 0;
    pq.push({0,nod_start});
    viz[nod_start] = true;

    while(!pq.empty())
    {
        int el = pq.top().second;
        viz[el] = 0;
        pq.pop();

        for(auto i : graf[el])
        {
            int vecin = i.first;
            int cost = i.second;
            if(dist[el] + cost < dist[vecin])
            {
                dist[vecin] = dist[el] + cost;
                if(viz[vecin] == false)
                {
                    viz[vecin] = true;
                    pq.push({-dist[vecin],vecin});
                }
            }
        }
    }
}

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

int main()
{
    fin>>n>>m;
    for(int i = 1;i <= m;i++)
    {
        int muchie1,muchie2,cost;
        fin>>muchie1>>muchie2>>cost;
        graf[muchie1].emplace_back(make_pair(muchie2,cost));
    }

    vector<bool>viz(n + 1);
    vector<int>dist(n + 1,inf);
    dijkstra(1,graf,viz,dist);
    for(int i = 2;i <= n;i++)
        dist[i] != inf ? fout<<dist[i]<<" " : fout<<0<<" ";
}