Pagini recente » Cod sursa (job #2683206) | Cod sursa (job #2505935) | Cod sursa (job #2569220) | Cod sursa (job #2537750) | Cod sursa (job #500808)
Cod sursa(job #500808)
#include <fstream.h>
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");
long int n, m, x, y, c[10000][10000], cost, d[100000], INF=32000;
void bellmanford (int);
int main ()
{
int i, j;
fin>>n>>m;
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
c[i][j]=INF;
for (i=1; i<=m; i++)
{
fin>>x>>y>>cost;
c[x][y]=cost;
}
bellmanford (1);
for (i=2; i<=n; i++)
fout<<d[i]<<' ';
fin.close();
fout.close ();
return 0;
}
void bellmanford(int x)
{
int inc, sf, q[100], i;
inc=sf=1;
q[inc]=x;
for (i=1; i<=n; i++)
d[i]=INF;
d[x]=0;
while (inc<=sf)
{
x=q[inc++];
for (i=1; i<=n; i++)
if (i!=x)
if (d[i]>d[x] + c[x][i])
{
d[i]=d[x] + c[x][i];
q[++sf]=i;
}
}
}
//varianta de pe arhiva campion
/*void bellmanford (int x0)
{
int i, j, k;
for (i=1; i<=n; i++)
d[i] = INF;
d[x0] = 0;
for (i=1; i<=n; i++)
{
for (j=1; j<=n; j++)
for (k=1; k<=n; k++)
if (d[j]!=INF && c[j][k]!=INF)
if (d[k]>d[j]+c[j][k])
{
d[k] = d[j]+c[j][k];
tata[k] = j;
}
}
}*/