Cod sursa(job #3376150)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 16 noiembrie 2026 13:08:12
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;

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

struct muchie{
    int x,c;
};

constexpr int N = 50005;

int n,m;

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

queue<int> q;

int main(){
    fin>>n>>m;

    for(int i=1; i<=m; ++i){
        int x,y,c;
        fin>>x>>y>>c;
        g[x].push_back({y,c});
    }

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

    q.push(1);
    viz[1]=1;

    nrViz[1]=1;
    while(!q.empty()){
        int nod = q.front();
        viz[nod]=0;
        q.pop();

        for(muchie e : g[nod]){
            int vecin = e.x;
            int cost = e.c;

            nrViz[vecin]=nrViz[nod]+1;

            if(dist[vecin]>dist[nod]+cost){
                dist[vecin]=dist[nod]+cost;

                if(nrViz[vecin]>=n){
                    fout<<"Ciclu negativ!";
                    return 0;
                }

                nrViz[vecin]=nrViz[nod]+1;

                if(viz[vecin]==0){
                    q.push(vecin);
                    viz[vecin]=1;
                }
            }
        }
    }

    for(int i=2; i<=n; ++i)
        fout<<dist[i]<<" ";

    return 0;
}