Pagini recente » Cod sursa (job #1775561) | Cod sursa (job #222389)
Cod sursa(job #222389)
#include<stdio.h>
#define N 1000
#define Inf 2000000000;
int n,x0,C[N][N],M[N],d[N];
void Citire();
void Afisare();
int main(){
int i,VfMin,j;
int dMin;
Citire();
for (j=1;j<n;j++)
{dMin=Inf;
for (i=1;i<=n;i++)
if (!M[i] && dMin>d[i]){
dMin=d[i];
VfMin=i;
}
M[VfMin]=1;
for (i=1;i<=n;i++)
if (!M[i]&& d[i]>dMin+C[VfMin][i])
d[i]=dMin+C[VfMin][i];
}
Afisare();
return 0;
}
void Citire(){
int i,j,m,x,y;
int c;
freopen("dijkstra.in","r",stdin);
scanf("%d %d",&n,&m);
for (i=1;i<=n;i++)
for (j=i+1;j<=n;j++)
C[i][j]=C[j][i]=Inf;
for (i=1;i<=m;i++){
scanf("%d %d %d",&x,&y,&c);
C[x][y]=c;
}
for (i=1;i<=n;i++) d[i]=C[1][i];
M[1]=1;
}
void Afisare(){
int i;
freopen("dijkstra.out","w",stdout);
for (i=2;i<=n;i++) printf("%d ",d[i]);
printf("\n");
}