Pagini recente » Cod sursa (job #2906871) | Cod sursa (job #504489) | Cod sursa (job #1955431) | Monitorul de evaluare | Cod sursa (job #2013996)
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
FILE *F=fopen("bellmanford.in", "r"), *G=fopen("bellmanford.out", "w");
int n, m, x, y, c, d[50005], knod[50005];
bitset<50005> inq;
queue<int> q;
vector<pair<int, int> > a[50005];
const int inf = 1 << 30;
int main()
{
fscanf(F, "%d %d ", &n, &m);
for(int i = 1; i <= m; ++ i)
{
fscanf(F, "%d %d %d ", &x, &y, &c);
a[x].push_back({y, c});
}
for(int i = 2; i <= n; ++ i) d[i] = inf;
q.push(1); inq[1] = 1;
vector<pair<int, int> > :: iterator it;
while(!q.empty())
{
x = q.front();
q.pop(); inq[x] = 0;
for(it = a[x].begin(); it != a[x].end(); ++ it)
if(d[(*it).f] > d[x] + (*it).s)
{
d[(*it).f] = d[x] + (*it).s;
if(!inq[(*it).f]) q.push((*it).f), inq[(*it).f] = 1;
if(++knod[(*it).f]>n)
{
fprintf(G, "Ciclu negativ!");
return 0;
}
}
}
for(int i = 2; i <= n; ++ i)
fprintf(G, "%d ", d[i]);
return 0;
}