Pagini recente » clasament-arhiva-educationala | Borderou de evaluare (job #45814) | Cod sursa (job #518550)
Cod sursa(job #518550)
#include<stdio.h>
#include<stdlib.h>
#define N 50001
typedef struct nod1
{long info1;
struct nod1 *next;}Nod1;
typedef struct
{Nod1 *prim1,*ultim1;}coada1;
typedef struct nod2
{long info2,cost;
struct nod2 *urm;}Nod2,*list;
typedef list graf[N];
long n,m,i,j,k,d[N],c;
graf g;
coada1 q1;
list r,q;
void push1(coada1 &q,long x)
{Nod1 *c=new Nod1;
c->info1=x;
c->next=NULL;
if(q.prim1==NULL)
q.prim1=q.ultim1=c;
else
{q.ultim1->next=c;
q.ultim1=c;}}
long pop1(coada1 &q)
{long x=q.prim1->info1;
Nod1 *t=q.prim1->next;
free(q.prim1);
q.prim1=t;
if(q.prim1==NULL)
q.ultim1=NULL;
return x;}
void push2(list &r,long x,long co)
{Nod2 *c=new Nod2;
c->info2=x;
c->cost=co;
c->urm=r;
r=c;}
int main()
{freopen("bellmanford.in","r",stdin);
freopen("bellmanford.out","w",stdout);
q1.prim1=q1.ultim1=NULL;
scanf("%ld%ld",&n,&m);
for(i=1;i<=n;i++)
{d[i]=50001;
g[i]=NULL;}
for(k=1;k<=m;k++)
{scanf("%ld%ld%ld",&i,&j,&c);
push2(g[i],j,c);}
d[1]=0;
push1(q1,1);
j=0;
while(q1.prim1!=NULL)
{i=pop1(q1);
for(r=g[i];r!=NULL;r=r->urm)
if(d[r->info2]>d[i]+r->cost)
{d[r->info2]=d[i]+r->cost;
push1(q1,r->info2);}
else
if(d[r->info2]>0&&d[i]>0)
j=1;
else
if(d[r->info2]<0&&d[i]<0)
k=1;
else
if(j==1&&k==1)
{printf("Ciclu negativ!");
return 0;}}
for(k=2;k<=n;k++)
if(d[k]>0)
printf("%ld ",d[k]%50001);
else
printf("%ld ",d[k]);
fclose(stdin);
fclose(stdout);
return 0;}