# Cod sursa(job #1857193)

Utilizator Data 25 ianuarie 2017 21:49:38 Algoritmul lui Dijkstra 100 cpp done Arhiva educationala 1.85 kb
``````#include<cstdio>
using namespace std;

const int nMax = 50000 + 5, mMax = 250000 + 5;
const int inf = 1 << 30;
int nod[mMax], urm[mMax], lst[nMax], val[mMax];
int d[nMax], pos[nMax], h[nMax];
int n,m, vf;

void change(int a, int b){
int aux = h[a];
h[a] = h[b];
h[b] = aux;
pos[h[a]] = a;
pos[h[b]] = b;
}

void down(int p){
int s = p << 1;
if(s <= vf){
if(s + 1 <= vf && d[h[s]] > d[h[s + 1]]) ++s;
if(d[h[s]] < d[h[p]]){
change(s, p);
down(s);
}
}
}

void up(int p){
int f = p >> 1;
if(f && d[h[f]] > d[h[p]]){
change(f, p);
up(f);
}
}

h[++vf] = nod;
pos[nod] = vf;
up(vf);
}

int pop(){
int nodC = h[1];
change(1, vf);
vf--;
down(1);

return nodC;
}

void dijkstra(){
vf = 0;
for(int i = 2 ; i <= n ; ++i) d[i] = inf;

int nodC, nextPos, vec;
while(vf){
nodC = pop();

nextPos = lst[nodC];
while(nextPos){
vec = nod[nextPos];

if(d[vec] > d[nodC] + val[nextPos]){
d[vec] = d[nodC] + val[nextPos];

if(pos[vec]) up(pos[vec]);
}

nextPos = urm[nextPos];
}
}
}

int main (){
FILE *in = fopen("dijkstra.in","r");
FILE *out = fopen("dijkstra.out","w");

fscanf(in,"%d%d", &n, &m);
int a, b, c;
for(int i = 1 ; i <= m ; ++i){
fscanf(in, "%d%d%d", &a, &b, &c);

nod[++vf] = b;
val[vf] = c;
urm[vf] = lst[a];
lst[a] = vf;
}

dijkstra();

for(int i = 2 ; i <= n ; i++){
d[i] = d[i] < inf ? d[i] : 0;
fprintf(out,"%d ", d[i]);
}
return 0;
}
``````