Cod sursa(job #3376159)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 16 noiembrie 2026 13:37:53
Problema Algoritmul lui Dijkstra Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.23 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

struct muchie{
    int x, c;
};

const int N = 50002;

vector<muchie> g[N];
int dist[N], viz[N], nrViz[N], n, m;

struct cmp{

public :
    bool operator() (muchie &a, muchie &b){
        if(a.c > b.c)
            return true;
        return false;
    }

};

priority_queue<muchie, vector<muchie>, cmp> H;

int main(){

    int i, j,  x, y, c;

    fin >> n >> m;

    for(i=1;i<=m;i++){

        fin >> x >> y >> c;

        g[x].push_back({y, c});

    }

    for(i=2;i<=n;i++)
        dist[i] = INT_MAX;

    H.push({1, 0});
    while(!H.empty()){

        muchie e  = H.top();
        int nod  = e.x;
       int cost = e.c;
        H.pop();

        if(viz[nod])
            continue;

        viz[nod] = 1;



        for(muchie vecin : g[nod]){

            if(!viz[vecin.x] && dist[vecin.x] > cost + vecin.c){
                dist[vecin.x] = vecin.c + cost;
                H.push({vecin.x, dist[vecin.x]});
            }

        }

    }

    for(i=2;i<=n;i++)
        if(dist[i] == INT_MAX)
            fout << "0 ";
        else
            fout << dist[i] << " ";

}