# Cod sursa(job #2764853)

Utilizator Data 22 iulie 2021 21:38:19 Algoritmul Bellman-Ford 85 cpp-64 done Arhiva educationala 1.78 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
using namespace std;

ifstream f ("bellmanford.in");
ofstream g ("bellmanford.out");

const int MAX_N = 50005;
const int INF = 0x3f3f3f3f;

vector < pair <int, int> > adj[MAX_N];
int dist[MAX_N], cnt_in_queue[MAX_N];

int main(void) {
int n, m;
f >> n >> m;
for (int i = 0; i < m; ++ i) {
int x, y, c;
f >> x >> y >> c;
}

queue <int> Q;
bool in_queue[MAX_N];
int negative_cycle = false;

for (int i = 1; i <= n; i++)
{
dist[i] = INF;
}

dist[1] = 0, Q.push(1), in_queue[1] = true;
while (!Q.empty() && !negative_cycle)  {
int x = Q.front();
Q.pop();
in_queue[x] = false;
for (int i = 0; i < adj[x].size(); i++)
if (dist[x] < INF)
{
if (dist[neighbour] > dist[x] + cost)
{
dist[neighbour] = dist[x] + cost;
if (!in_queue[neighbour])
{
if (cnt_in_queue[neighbour] > n)
negative_cycle = true;
else
{
Q.push(neighbour);
in_queue[neighbour] = true;
cnt_in_queue[neighbour] ++;
}
}
}
}
}

if (!negative_cycle) {
for (int i = 2; i <= n; ++ i)
g << dist[i] << " ";
}
else
g << "Ciclu negativ!\n";

return 0;
}
``````