Cod sursa(job #704884)
/*#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define TR(C, i)\
for(typeof(C.begin()) i = C.begin(); i != C.end(); i++)
using namespace std;
ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");
const int oo = 0x3f3f3f3f;
const int nmax = 50010;
int N, M;
vector< pair<int, int> > G[nmax];
int D[nmax];
void citire()
{
in >> N >> M;
for(int i = 1; i <= M; ++i)
{
int x, y, d;
in >> x >> y >> d;
G[x].push_back(make_pair(y, d));
}
}
struct cmp
{
bool operator()(const int &a, const int &b)const
{
return D[a] > D[b];
}
};
priority_queue <int, vector<int>, cmp> Q;
bool In[nmax];
int scos[nmax];
void solve()
{
memset(D, 0x3f, sizeof(D));
D[1] = 0;
In[1] = true;
Q.push(1);
int nod;
while(!Q.empty())
{
nod = Q.top();
Q.pop();
In[nod] = 0;
++scos[nod];
if(scos[nod] > N)
{
out << "Ciclu negativ!";
return;
}
TR(G[nod], it)
if(D[it->first] > D[nod] + it->second)
{
D[it->first] = D[nod] + it->second;
if(In[it->first])continue;
Q.push(it->first);
In[it->first] = 1;
}
}
int i;
for(i = 2; i <= N; i++)
out << D[i] << ' ';
out << '\n';
}
int main()
{
citire();
solve();
return 0;
}*/
#include <cstdio>
#include <vector>
#include <queue>
#define N 50003
#define I 999999999
using namespace std;
struct nod
{
int v;
int c;
};
int n;
int d[N];
int nr[N];
bool 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();
viz[v] = 0;
++ 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;
}