Cod sursa(job #1922779)

Utilizator stefanvdpruna stefan stefanvd Data 10 martie 2017 18:53:13
Problema Algoritmul Bellman-Ford Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.9 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
struct nod
{
    nod* urm;
    int inf,cost;
};
nod* v[1000];
int cost[1000],n,m,i;

int main()
{
    int inf=9999999;
    f>>n>>m;
    int x,y,z;
for(i=1;i<=m;i++)
{
    f>>x>>y>>z;
    if(v[x]!=NULL)
    {
    nod* q=new nod;
    q->inf=y;
    q->cost=z;
    q->urm=v[x]->urm;
    v[x]->urm=q;
    }
    else
    {
    nod* q=new nod;
    q->inf=y;
    q->cost=z;
    q->urm=NULL;
    v[x]=q;
    }
}
for(i=1;i<=n;i++)
    cost[i]=inf;
cost[1]=0;
for(i=1;i<=n;i++)
{
    if(v[i])
    {
        nod* p=v[i];
        while(p)
        {
            if(cost[p->inf]>cost[i]+p->cost)
                cost[p->inf]=cost[i]+p->cost;
                p=p->urm;
        }
    }
}
for(i=1;i<=n;i++)
    if(cost[i]!=0) g<<cost[i]<<" ";
    return 0;
}