Cod sursa(job #2215120)
Utilizator | Filip A Shutterfly | Data | 21 iunie 2018 04:37:12 |
---|---|---|---|
Problema | Algoritmul lui Dijkstra | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.6 kb |
#include<fstream.h>
const int inf=2000000;
int a[250001][4],d[50001],n,k,ok=1,i,j,c,m;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int main()
{
f>>n>>m;int nr=1;
for(i=1;i++<=n;)d[i]=inf;d[1]=0;
for(i=1;i++<=m;)
{ f>>a[i][1]>>a[i][2]>>a[i][3];
if(a[i][1]==1)d[a[i][2]]=a[i][3];
}
while(ok && nr<n)
{ok=0;
for(k=1;k++<=m;)
{
i=a[k][1];j=a[k][2];c=a[k][3];
if(d[j]>d[i]+c){d[j]=d[i]+c;ok=1;}
}
nr++;
}
for(i=2;i++<=n;)if(d[i]<inf)g<<d[i]<<" ";
else g<<0<<" ";
return 0;
}