Pagini recente » Istoria paginii utilizator/ursulfioros | Borderou de evaluare (job #1049526) | Cod sursa (job #1813862)
#include <iostream>
#include <fstream>
#define inf 2147483647
using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
int n,m,a,b,c;
struct nod{
int vecin;
int cost;
struct nod *urm;
}*l[50001],*q;//liste cu drumurile care pornesc din fiecare nod si valoarea lor
int viz[50001];//are valoarea 0 daca nodul nu a fost vizitat si pozitia sa in heap in caz contrar
int h[50001],nr;//heapul si numarul de elemente din acesta
int d[50001],mn;//distantele pana la fiecare nod si nodul minim curent
void add_h(int nr){
//incepem de pe pozitia curenta
int poz=nr;
//cat timp mai exista noduri in heap si tatal are valoare mai mare decat fiul
while(poz>1 && h[poz/2]>h[poz]){
//interschimbam tatal cu fiul
int t=h[poz/2];
h[poz/2]=h[poz];
h[poz]=t;
//interschimbam pozitiile acestora in vectorul viz
t=viz[h[poz/2]];
viz[h[poz/2]]=viz[h[poz]];
viz[h[poz]]=t;
//continuam cautarea pentru noul tata
poz/=2;
}
}
void del_vf(int &nr){
//interschimbam primul cu ultimul elemente si scadem numarul de elemente din heap
h[1]=h[nr];
int t=viz[h[1]];
viz[h[1]]=viz[h[nr]];
viz[h[nr]]=t;
--nr;
//incepem cautarea din radacina
int poz=1;
while(2*poz<=nr){
int fiu=2*poz;
//daca exista descendent drept si are valoare mai mica decat cel stang, il consideram fiu optim
if(fiu+1<=nr && h[fiu+1]<h[fiu])
++fiu;
//daca fiul optim are valoare mai mica decat tatal
if(h[fiu]<h[poz]){
//interschimbam tatal cu fiul
int t=h[poz];
h[poz]=h[fiu];
h[fiu]=t;
//interschimbam pozitiile acestora in vectorul viz
t=viz[h[poz]];
viz[h[poz]]=viz[h[fiu]];
viz[h[fiu]]=t;
//continuam cautarea pentru fiu
poz=fiu;
}
//atfel oprim cautarea
else poz=nr+1;
}
}
void dijkstra(int p){
//initializam toate distantele cu +inf
for(int i=2;i<=n;++i)
d[i]=inf;
//parcurgem nodurile care au drum din primul nod
q=l[p];
while(q!=NULL){
//modificam distanta in vector
d[q->vecin]=q->cost;
//crestem numarul de elemente din heap si il adaugam pe ultima pozitie
++nr;
viz[q->vecin]=nr;
h[nr]=q->vecin;
//ne asiguram sa pastram proprietatea de heap
add_h(nr);
q=q->urm;
}
/*for(int i=1;i<=nr;++i)
out<<h[i]<<" ";
out<<endl<<endl;*/
while(nr>0){
//scoatem radacina(elementul minim) din heap si o marcam ca nevizitata
mn=h[p];
viz[mn]=0;
//ne asiguram sa pastram proprietatea de heap
del_vf(nr);
//parcurgem nodurile care au drum din nodul minim
q=l[mn];
while(q!=NULL){
//daca distanta prin drumul minim este mai mica
if(d[q->vecin]>d[mn]+q->cost){
//actualizam distanta
d[q->vecin]=d[mn]+q->cost;
//adaugam nodul in heap daca nu exista deja in acesta
if(viz[q->vecin]==0){
++nr;
viz[q->vecin]=nr;
h[nr]=q->vecin;
add_h(nr);
}
//altfel ne asiguram ca nodul este intr-o pozitie corecta
else
add_h(viz[q->vecin]);
}
q=q->urm;
}
}
}
int main()
{
//citim numarul de noduri si muchii
in>>n>>m;
//memoram drumurile si distantele acestora care incep din fiecare nod
for(int i=1;i<=m;++i){
in>>a>>b>>c;
q=new nod;
q->vecin=b;
q->cost=c;
//adaugam la sfarsitul listei
q->urm=l[a];
l[a]=q;
}
//stabilim distanta minima de la modul 1 catre toate celelalte noduri
dijkstra(1);
for(int i=2;i<=n;++i)
out<<d[i]<<" ";
return 0;
}