# Cod sursa(job #2738651)

Utilizator Data 6 aprilie 2021 10:35:30 Algoritmul Bellman-Ford 100 cpp-64 done Arhiva educationala 1.59 kb
``````#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

typedef pair < int, int > Edge;

const int NMAX = 5e4 + 1;
const int INF = 1e9;

int N, M;
vector < Edge > G[NMAX];

int d[NMAX];
bool Sel[NMAX];
int cnts[NMAX];

queue < int > Q;

{
f.tie(nullptr);

f >> N >> M;

for(int i = 1; i <= M; ++i)
{
int X = 0, Y = 0, C = 0;
f >> X >> Y >> C;

G[X].push_back({C, Y});
}

return;
}

static inline void Solve ()
{
for(int i = 1; i <= N; ++i)
d[i] = INF, Sel[i] = 0;

d[1] = 0, Sel[1] = 1, ++cnts[1], Q.push(1);

while(!Q.empty())
{
int Node = Q.front();
Sel[Node] = 0, Q.pop();

for(auto it : G[Node])
if(d[Node] + it.first < d[it.second])
{
d[it.second] = d[Node] + it.first;

if(Sel[it.second])
continue;
else
{
++cnts[it.second];

if(cnts[it.second] > N)
{
g << "Ciclu negativ!" << '\n';

return;
}

Sel[it.second] = 1, Q.push(it.second);
}
}
}

for(int i = 2; i <= N; ++i)
{
g << d[i];

if(i != N)
g << ' ';
}

g << '\n';

return;
}

int main()
{