Cod sursa(job #3376148)

Utilizator LucaMirsolea14Luca Mirsolea LucaMirsolea14 Data 16 noiembrie 2026 13:05:22
Problema Algoritmul Bellman-Ford Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.29 kb
#include<bits/stdc++.h>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.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, x, y, c;

    fin >> n >> m;

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

        fin >> x >> y >> c;

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

    }

    for(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;

            if(dist[vecin] > dist[nod] + cost){
                dist[vecin] = dist[nod] + cost;
                if(viz[vecin] == 0){
                    Q.push(vecin);
                    viz[vecin] = 1;

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

        }

    }

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

}