Cod sursa(job #862027)
#include <fstream>
#define DMAX 1000
#define INFINIT 1000
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
int n, m, vf_start;
int tata[DMAX];
int Cmin[DMAX];
int C[DMAX][DMAX];
short int M[DMAX];
void citire();
void init();
void dijkstra();
void bellman_ford();
void afisare();
int main()
{
citire();
init();
//dijkstra();
bellman_ford();
afisare();
return 0;
}
void citire()
{
fin >> n >> m ;
vf_start=1;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
C[i][j] = INFINIT;
C[i][i] = 0;
}
}
int i,x,y,c;
for(i = 1; i <= m; i++)
{
fin >> x >> y >> c;
C[x][y] = c;
}
fin.close();
}
void init()
{
M[vf_start] = 1;
int i;
for(i = 1; i <= n; i++)
{
Cmin[i] = C[vf_start][i];
tata[i] = vf_start;
}
tata[vf_start] = 0;
}
int minim()
{
int res = 0, vfmin = 0;
int i = 1;
for(i = 1; i <= n; i++)
{
if(M[i] == 0 )
{
res = Cmin[i];
vfmin = i;
break;
}
}
for(i; i <= n; i++)
{
if(Cmin[i] < res && M[i] == 0 )
{
res = Cmin[i];
vfmin = i;
}
}
M[vfmin] = 1;
return vfmin;
}
void dijkstra()
{
int i, x, vfmin;
for(i = 1; i <= n-1; i++)
{
vfmin = minim();
for(x = 1; x <= n; x++)
{
if(M[x] == 0 && Cmin[x] > Cmin[vfmin] + C[vfmin][x])
{
Cmin[x] = Cmin[vfmin] + C[vfmin][x];
tata[x] = vfmin;
}
}
}
}
void afisare()
{
int i;
for(i = 2; i <= n; i++)
{
fout << Cmin[i] <<' ';
}
fout.close();
}
void bellman_ford()
{
int i, x,y,op;
for(i = 1; i <= n; i++)
{
op=0;
for(x = 1; x <= n; x++)
{
for(y=1;y<=n;y++)
if( Cmin[y] > Cmin[x] + C[x][y])
{
Cmin[y] = Cmin[x] + C[x][y];
tata[y] = x;
op=1;
}
}
}
if(op)
{fout<<"ciclu negativ"; fout.close();}
else
afisare();
}