Pagini recente » Cod sursa (job #741500) | Cod sursa (job #3038010) | Cod sursa (job #3274596) | Cod sursa (job #2343907) | Cod sursa (job #2606291)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int val_max =20005;
struct data{
int val;
unsigned short dest;
}adaugare,nimic,curent;
struct nod{
data val;
struct nod *dr;
struct nod *st;
}*radacina;
bool operator <(data a , data b){
return a.val > b.val;
}
vector <data> v[50005];
int dist[50005];
void heap_Insert(data x , nod *&actual){
if(actual == NULL){
actual= new nod;
actual->val= x;
actual->st= NULL;
actual->dr= NULL;
return;
}
if(x.val < actual->val.val )
swap(x,actual->val );
if(actual->dr == NULL){
heap_Insert(x , actual->dr );
return;
}
if(actual->st == NULL){
heap_Insert(x , actual->st );
return;
}
if(actual->st->val.val < actual->dr->val.val)
heap_Insert(x, actual->st);
else
heap_Insert(x, actual->dr);
}
data heap_Remove(nod *actual){
nimic.val= val_max;
if(actual == NULL)
return nimic;
data returnare= actual->val;
int st;
int dr;
if(actual->st != NULL)
st= actual->st->val.val;
else
st=val_max;
if(actual->dr != NULL)
dr= actual->dr->val.val;
else
dr= val_max;
if(st<dr)
actual->val= heap_Remove(actual->st);
else
actual->val= heap_Remove(actual->dr);
return returnare;
}
bool heap_Is_Empty(nod *radacina){
if(radacina == NULL)
return true;
if(radacina->val.val == val_max )
return true;
return false;
}
void reinit_heap_propriu(){
while(heap_Remove(radacina).val != val_max);
}
int dijkstra(int n){
adaugare.dest= 1;
adaugare.val= 0;
heap_Insert(adaugare,radacina);
while(!heap_Is_Empty(radacina)){
curent=heap_Remove(radacina);
for(int i=0; i<v[curent.dest].size();i++ ){
adaugare.val= curent.val + v[ curent.dest ][i].val;
adaugare.dest= v[ curent.dest ][i].dest;
heap_Insert(adaugare, radacina);
}
}
return 0;
}
priority_queue <data> heap;
void reinit_heap(){
while(!heap.empty())
heap.pop();
}
void dijkstra_heap(int n){
adaugare.dest= 1;
adaugare.val= 0;
heap.push(adaugare);
while(!heap.empty()){
curent=heap.top();
heap.pop();
if(dist[curent.dest] == 0)
dist[curent.dest]=curent.val;
for(int i=0; i<v[curent.dest].size();i++ )
if( dist[ v[ curent.dest ][i].dest ] == 0 ){
adaugare.val= curent.val + v[ curent.dest ][i].val;
adaugare.dest= v[ curent.dest ][i].dest;
heap.push(adaugare);
}
}
}
int main()
{
//Citire vector
int i,j,n,m,a,b,c;
fin>>n>>m;
for(i=0;i<m;i++){
fin>>a>>b>>c;
adaugare.val=c;
adaugare.dest=b;
v[a].push_back(adaugare);
}
//Dijkstra pentru n noduri
dijkstra_heap(i);
//fout<<dijkstra(i)<<" ";
for(i=2;i<=n;i++)
fout<<dist[i]<<" ";
return 0;
}