Cod sursa(job #1603001)
Utilizator | Ouatu Bogdan-Ioan BogdanOuatu | Data | 17 februarie 2016 09:14:23 |
---|---|---|---|
Problema | Algoritmul lui Dijkstra | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.68 kb |
#include <fstream>
#define INF 9999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int a[250004][3],n,m,d[50003];
int main()
{
int i,ok=1;
fin>>n>>m;
for(i=1;i<=n;i++)d[i]=INF;
d[1]=0;
for(i=0;i<m;i++)
fin>>a[i][0]>>a[i][1]>>a[i][2];
while(ok)
{
ok=0;
for(i=0;i<m;i++)
if(d[a[i][1]]>d[a[i][0]]+a[i][2])
{
d[a[i][1]]=d[a[i][0]]+a[i][2];
ok=1;
}
}
for(i=2;i<=n;i++)
if(d[i]<INF)
fout<<d[i]<<' ';
else fout<<"0 ";
fin.close();
fout.close();
return 0;
}