# Cod sursa(job #611542)

Utilizator Data 1 septembrie 2011 21:29:18 Algoritmul lui Dijkstra 20 cpp done Arhiva educationala 2.74 kb
``````#include <iostream>
#include <fstream>
#include <stdlib.h>
#include <vector>
#include <vector>

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)
{
int T;

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

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

void down_heap(int poz)
{
if (poz <= nr_heap)
return;

int L = 2 * poz;
int R = 2 * poz + 1;
int 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;

//swap(loc[heap[poz]], loc[heap[aux_poz]]);
loc[heap[poz]] = aux_poz;
loc[heap[aux_poz]] = poz;

swap(heap[poz], heap[aux_poz]);
down_heap(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;
insert_heap(start_node);

while (nr_heap)
{
int nod = heap[1];
delete_heap();
used[nod] = 1;

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;
/*
if (loc[(*it)->right] > 0)
up_heap(loc[(*it)->right]);
else
*/
if (!used[(*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] <<" ";
};
``````