infoarena

#include <cstdio>
#include <cstring>
#define INFI 0x3f3f3f3f
#define DM 250001
#define DN 50001

struct nod {
    int x,cost;
    nod *urm;
}*v[DN];

int m,n,dist[DN],pr[DN];

void adaugare(int x,int y,int cost) {
    nod *p;
    p=new nod;
    p->cost=cost;
    p->x=y;
    p->urm=v[x];
    v[x]=p;
}

void relaxare(int u,int v,int cost) {
    if(dist[v]>dist[u]+cost) {
        dist[v]=dist[u]+cost;
        pr[v]=u;
    }
}

bool bellman_ford() {
    int i;
    nod *p;
    for(i=1; i<n; i++)
       for(p=v[i]; p!=NULL; p=p->urm)
            relaxare(i,p->x,p->cost);
    for(i=1; i<n; i++) for(p=v[i]; p!=NULL; p=p->urm)
        if(dist[i]>dist[p->x]+p->cost) return false;
    return true;
}

void initializareSU() {
    memset(dist,INFI,sizeof(dist));
    memset(pr,0,sizeof(pr));
    dist[1]=0;
}

void afisare() {
    nod *p;
    int k;
    for(k=1; k<=n; k++) {
        p=v[k];
        printf("%d:",k);
        while(p) {
            printf("%d ",p->x);
            p=p->urm;
        }
        printf("\n");
    }
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    int i,x,y,c;
    scanf("%d %d",&n,&m);
    for(i=1; i<=m; i++)
        scanf("%d %d %d",&x,&y,&c), adaugare(x,y,c);
    initializareSU();
    if(!bellman_ford()) printf("Ciclu negativ!\n");
    else for(i=2; i<=n; i++) printf("%d ",dist[i]);
    //afisare();
    return 0;
}

struct lista
{
    int inf,c;
    lista *nod;
} *g[nmax];