Cod sursa(job #836679)

Utilizator RadEmanuelRad Emanuel RadEmanuel Data 16 decembrie 2012 14:44:45
Problema Algoritmul lui Dijkstra Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<cstdio>
#define INF 2147483600
using namespace std;
FILE *fin=fopen("dijkstra.in","r");
FILE *fout=fopen("dijkstra.out","w");
int i,j,k,n,m,t[5000][5000],d[50003],a,b,c;

int main()
{
    fscanf(fin,"%d%d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(fin,"%d%d%d",&a,&b,&c);
        t[a][b]=c;
    }
    for(i=1;i<=n;++i)
        for(j=1;j<=n;++j)
        {
            if(!t[i][j] && i!=j) t[i][j]=INF;
            if(i==1) d[j]=t[i][j];
        }
    int k=1;
    while(k<=n)
    {
        for(j=1;j<=n;++j)
            if(d[j]>t[1][k]+t[k][j] && k!=1 && j!=k && t[1][k]!=INF && t[k][j]!=INF)
                d[j]=t[1][k]+t[k][j];
        ++k;
    }
    for(i=2;i<=n;++i)
        if(d[j]==INF) fprintf(fout,"0 ");
                 else fprintf(fout,"%d ",d[i]);
    return 0;
}