Cod sursa(job #1915958)
Utilizator | Data | 8 martie 2017 23:17:22 | |
---|---|---|---|
Problema | Algoritmul lui Dijkstra | Scor | 90 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.61 kb |
#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i,m,n,a[250001],b[250001],cost[250001],d[50001],ok,Max;
int main()
{f>>n>>m;
Max=(1<<30);
for(i=1;i<=n;i++)
d[i]=Max;
for(i=1;i<=m;i++){
f>>a[i]>>b[i]>>cost[i];
if(a[i]==1)
d[b[i]]=cost[i];
}
ok=0;
while(ok==0){
ok=1;
for(i=1;i<=m;i++){
if(d[b[i]]>d[a[i]]+cost[i]){
d[b[i]]=d[a[i]]+cost[i];
ok=0;
}
}
}
for(i=2;i<=n;i++)
if(d[i]==Max)
g<<0<<" ";
else
g<<d[i]<<" ";
return 0;
}