Cod sursa(job #2013996)

Utilizator workwork work work Data 22 august 2017 18:19:28
Problema Algoritmul Bellman-Ford Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#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;
}