Pagini recente » Cod sursa (job #2570646) | Cod sursa (job #2059667) | Cod sursa (job #2801970) | Cod sursa (job #260838) | Cod sursa (job #890150)
Cod sursa(job #890150)
#include <fstream>
#include <process.h>
#include <cstdlib>
using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");
struct nod{int inf,c;
nod *leg;}*li[500],*p;
int i,j,n,k,m,start,c=30000,x,y,cost;
int t[100],d[100];
int minimizeaza()
{
int ok,j;
ok=false;
for(j=1;j<=n;++j)
{
p=new nod;
p=li[j];
while(p!=NULL)
{
if(d[p->inf]>d[j]+p->c)
{
ok=true;
d[p->inf]=d[j]+p->c;
t[p->inf]=j;
}
p=p->leg;
}
}
return ok;
}
void bellman_ford()
{
int ok,i;
for(i=1;i<=n;++i)
{
t[i]=0;
d[i]=c;
}
d[start]=0;
for(i=1;i<n;++i)
ok=minimizeaza();
ok=minimizeaza();
if(ok)
{
fout<<"Ciclu negativ!";
exit(0);
}
}
void drum(int x)
{
if(x)
drum(t[x]);
if(x!=0)
fout<<x<<" ";
}
int main()
{
fin>>n>>m;
for(i=1;i<=m;++i)
{
fin>>x>>y>>cost;
p=new nod;
p->leg=li[x];
p->inf=y;
p->c=cost;
li[x]=p;
}
start=1;
bellman_ford();
for(i=1;i<=n;++i)
if(i!=start)
{
fout<<"cost "<<d[i]<<" prin ";
drum(i);
fout<<'\n';
}
return 0;
}