Cod sursa(job #3376155)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 16 noiembrie 2026 13:18:07
Problema Algoritmul lui Dijkstra Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 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;

queue<int> Q;

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;

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

        /// gasesc nodul care are in dist[] valoare minima si e nevizitat

        int mini = INT_MAX, nodMin=-1;

        for(j=1;j<=n;j++){

            if(viz[j] == 0 && mini > dist[j]){
                mini = dist[j];
                nodMin = j;
            }

        }

        if(nodMin != -1){

            viz[nodMin] = 1;

            /// actualizez distantele de la nodMin la toate celelate noduri

            for(muchie vecin : g[nodMin]){

                if(!viz[vecin.x] && dist[vecin.x] > dist[nodMin] + vecin.c){
                    dist[vecin.x] = dist[nodMin] + vecin.c;
                }

            }

        }

    }

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

}