# Cod sursa(job #611550)

Utilizator Data 1 septembrie 2011 21:41:59 Algoritmul lui Dijkstra 50 cpp done Arhiva educationala 2.67 kb
``````#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <queue>

using namespace std;

void solve();
void check();
void print();

const int MAX_NODES = 50001;
const int MAX_EDGES = 250001;

const int oo = 0x3f3f3f3f;

void solve();
void check();
void print();

struct node
{
int right, cost;
node(int right, int cost) { this->right = right; this->cost = cost; };
};

int main()
{
solve();
check();
print();

return 0;
}

int n, m;
vector< struct node * > List[MAX_NODES];
int dist[MAX_NODES];
int loc[MAX_NODES];
int used[MAX_NODES];

/*	begin heap	*/
int heap[MAX_NODES];
int nr_heap;

void up_heap(int poz)
{
register int T;

while (true)
{
if (poz <= 1) return;
T = poz >> 1;

if (dist[heap[T]] > dist[heap[poz]])
{
swap(heap[T], heap[poz]);
poz = T;
}
else
break;
}
}

void down_heap(int poz)
{
register int L;
register int R;
register int aux_poz;

while (true)
{
if (poz <= nr_heap)
return;

L = 2 * poz;
R = 2 * poz + 1;

aux_poz = poz;

if (L <= nr_heap)
if (dist[heap[L]] < dist[heap[aux_poz]])
aux_poz = L;

if (R <= nr_heap)
if (dist[heap[R]] < dist[heap[aux_poz]])
aux_poz = R;

if (aux_poz == poz)
return;
/*
loc[heap[poz]] = aux_poz;
loc[heap[aux_poz]] = poz;
*/
swap(heap[poz], heap[aux_poz]);
poz = aux_poz;
}
}

void insert_heap(int info)
{
heap[++nr_heap] = info;
loc[info] = nr_heap;
up_heap(nr_heap);
}

void delete_heap()
{
loc[heap[nr_heap]] = 1;
loc[heap[1]] = -1;
heap[1] = heap[nr_heap];
--nr_heap;
down_heap(1);
}
/*	end heap	*/

{
int left, right, cost;

fstream f("dijkstra.in", ofstream::in);
f >> n >> m;

for (int i = 1; i <= m ; ++i)
{
f >> left >> right >> cost;
List[left].push_back(new node(right, cost));
}
};

void solve()
{
int start_node = 1;
for (int i = 1; i <= n; ++i)
dist[i] = oo;
dist[start_node] = 0;
//priority_queue<int> Q;

//Q.push(start_node);
insert_heap(start_node);

while (nr_heap)//!Q.empty())
{
int nod = heap[1];//Q.top();
//Q.pop();
delete_heap();

for (vector<struct node *>::iterator it = List[nod].begin() ; it != List[nod].end(); it++)
if (dist[(*it)->right] > dist[nod] + (*it)->cost )
{
dist[(*it)->right] = dist[nod] + (*it)->cost;

//Q.push((*it)->right);
insert_heap((*it)->right);
}
}
};

void check()
{
};

void print()
{
ofstream ofs("dijkstra.out", ofstream::out);
for (int i = 2; i <= n; ++i)
if (dist[i] == oo)
ofs << "0 ";
else
ofs << dist[i] <<" ";
};
``````