Cod sursa(job #836679)
#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;
}