# Cod sursa(job #2764876)

Utilizator Data 23 iulie 2021 00:15:43 Algoritmul Bellman-Ford 100 cpp-64 done Arhiva educationala 1.69 kb
``````#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int INFINITY = (1 << 31) - 1;
const int MAX = 50001;

int n, m;
int dist[MAX], cntInQueue[MAX];
bool onQueue[MAX];
vector <pair <int, int>> V[MAX];
queue <int> Q;

{
f >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y, z;
f >> x >> y >> z;
V[x].push_back(make_pair(y, z));
}
}

bool BellmanFord(int startNode)
{
for (int i = 1; i <= n; i++)
{
dist[i] = INFINITY;
}

dist[startNode] = 0;
Q.push(startNode);
onQueue[startNode] = true;
cntInQueue[startNode]++;

while (Q.empty() == false)
{
int node = Q.front();
Q.pop();
onQueue[node] = false;
cntInQueue[node]++;

if (cntInQueue[node] >= n)
{
return false;
}

for (int i = 0; i < V[node].size(); i++)
{
int neighbour = V[node][i].first;
int cost = V[node][i].second;
if (dist[node] + cost < dist[neighbour])
{
dist[neighbour] = dist[node] + cost;
if (onQueue[neighbour] == false)
{
Q.push(neighbour);
onQueue[neighbour] = true;
}
}
}
}
return true;
}

int main()
{