Cod sursa(job #704795)
#include <cstdio>
#include <vector>
#include <queue>
#define N 100
#define I 999999999
using namespace std;
struct nod
{
int v;
int c;
};
int n;
int d[N];
int nr[N];
int viz[N];
struct cmp
{
bool operator () (const int &a, const int &b) const
{
return d[a] > d[b];
}
};
vector < nod > g[N];
priority_queue < int, vector < int >, cmp > q;
void citire()
{
freopen ("bellmanford.in", "r", stdin);
int m;
scanf ("%d %d ", &n, &m);
while (m --)
{
int v;
nod aux;
scanf ("%d %d %d ", &v, &aux.v, &aux.c);
g[v].push_back (aux);
}
}
int b_f(int vf)
{
for (int i = 1; i <= n; d[i] = I, ++ i);
d[vf] = 0;
viz[vf] = 1;
q.push (vf);
while (!q.empty())
{
int v = q.top();
q.pop();
++ nr[v];
if (nr[v] > n)
return 0;
unsigned int m = g[v].size();
for (unsigned int i = 0; i < m; ++ i)
{
nod aux = g[v][i];
if (d[v] + aux.c < d[aux.v])
{
d[aux.v] = d[v] + aux.c;
if (!viz[aux.v])
{
q.push (aux.v);
viz[aux.v] = 1;
}
}
}
}
return 1;
}
void afisare()
{
for (int i = 2; i <= n; ++ i)
if (d[i] == I)
printf ("0 ");
else
printf ("%d ", d[i]);
printf ("\n");
}
int main()
{
citire();
freopen ("bellmanford.out", "w", stdout);
if (!b_f(1))
printf ("Ciclu negativ!\n");
else
afisare();
return 0;
}