# Cod sursa(job #2764854)

Utilizator Data 22 iulie 2021 22:22:31 Algoritmul Bellman-Ford 100 cpp-64 done Arhiva educationala 1.17 kb
``````#include<iostream>
#include<vector>
#include<queue>
#include<fstream>
#define inf 0x3f3f3f3f
#define NMAX 50010
#define MMAX NMAX*5
using namespace std;
bool inQ[NMAX];
vector<pair<int, int>> g[NMAX];
int d[NMAX];
int viz[NMAX];
int n, m;

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

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

bool bellmanford(int src)
{
for (int i = 1; i <= n; i++)
d[i] = inf,viz[i]=0;
d[src] = 0;
viz[src]++;
inQ[src] = true;
{
viz[extract]++;
inQ[extract] = false;
if (viz[extract] >= n)
return false;
for (auto& it : g[extract])
{
int vec = it.first;
int cost = it.second;
if (d[extract] + cost < d[vec])
{
d[vec] = d[extract] + cost;
if (!inQ[vec])
{

}
}
}

}
return true;
}

int main()
{
cit();
if (!bellmanford(1))
gg << "Ciclu negativ!";
else
for (int i = 2; i <= n; i++)
gg << d[i] << " ";
}``````