Cod sursa(job #2018139)

Utilizator dacianouaPapadia Mortala dacianoua Data 3 septembrie 2017 16:42:09
Problema Algoritmul lui Dijkstra Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <stdio.h>
#include <limits.h>
#include <stdlib.h>
#define nmax 50000
#define mmax 250000
using namespace std;
FILE *fin,*fout;
int n,m,viz[nmax+5],l[nmax+5];
struct nod
{
    int info,cost;
    nod *next;
}*v[nmax+5],*c,*d;
int main()
{
    int x,y,z;
    fin=fopen("dijkstra.in","r");
    fout=fopen("dijkstra.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        v[i]=new nod;
        v[i]->info=i;
        v[i]->next=0;
    }
    for(int i=2;i<=n;i++)
        l[i]=INT_MAX;
    l[1]=0;
    for(int i=1;i<=m;i++)
    {
        fscanf(fin,"%d %d %d",&x,&y,&z);
        c=v[x];
        while(c->next)
            c=c->next;
        d=new nod;
        d->info=y;
        d->cost=z;
        d->next=0;
        c->next=d;
        c=v[y];
        while(c->next)
            c=c->next;
        d=new nod;
        d->info=x;
        d->cost=z;
        d->next=0;
        c->next=d;
        if(x==1)
            l[y]=z;
        if(y==1)
            l[x]=z;
    }
    int k=1,minv,ok=1;viz[1]=1;
    while(ok)
    {
        minv=INT_MAX;
        c=v[k];
        while(c->next)
        {
            c=c->next;
            if(l[c->info]<minv &&!viz[c->info])
                {minv=l[c->info];k=c->info;}
        }
        if(minv!=INT_MAX)
        {
            viz[k]=1;
            d=v[k];
            while(d->next)
            {
                d=d->next;
                if(!viz[d->info] && l[d->info]>l[k]+d->cost)
                    l[d->info]=l[k]+d->cost;
            }
        }
        else ok=0;
    }
    for(int i=2;i<=n;i++)
    {
        if(i==n)
        {   if(l[i]==INT_MAX)
            fprintf(fout,"%d",0);
            else
            fprintf(fout,"%d ",l[i]);}
        else
            {   if(l[i]==INT_MAX)
            fprintf(fout,"%d",0);
            else
            fprintf(fout,"%d ",l[i]);}
    }
    return 0;
}