# Cod sursa(job #2380444)

Utilizator Data 14 martie 2019 22:01:14 Algoritmul lui Dijkstra 90 cpp-64 done Arhiva educationala 2.1 kb
``````#include <bits/stdc++.h>
#include <unordered_set>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

int n, x, m, a, b;
vector<vector<pair<int, int>>> edges;
vector<int> cost;

class Heap
{
private:
vector<int> heap;

void up(int startIndex)
{
for (int index = startIndex, parentIndex = index >>= 1; parentIndex > 0; index >>= 1, parentIndex >>= 1)
if (cost[heap[index]] < cost[heap[parentIndex]])
swap(heap[index], heap[parentIndex]);
else
return;
}

void down(int startIndex)
{
for (int index = startIndex, childIndex = index << 1;
childIndex < heap.size();
index = childIndex, childIndex <<= 1)
{
if (childIndex + 1 < heap.size() && cost[heap[childIndex]] > cost[heap[childIndex + 1]])
++childIndex;

if (cost[heap[index]] > cost[heap[childIndex]])
swap(heap[index], heap[childIndex]);
else
return;
}
}

public:
Heap()
{
heap.push_back(0); // index from 1
}

void push(int x)
{
heap.push_back(x);
up(heap.size() - 1);
}

int pop()
{
int min = heap[1];

swap(heap[1], heap[heap.size() - 1]);
heap.pop_back();
down(1);

return min;
}

bool empty()
{
return heap.size() == 1;
}
};

int main()
{
f >> n >> m;
edges.resize(n + 1);
cost.resize(n + 1, INT_MAX);

while (m--)
f >> x >> a >> b,
edges[x].push_back({ a, b });

Heap heap;

heap.push(1);
cost[1] = 0;
while (!heap.empty())
{
int x = heap.pop();
for (auto& next : edges[x])
if (cost[next.first] > cost[x] + next.second)
cost[next.first] = cost[x] + next.second,
heap.push(next.first);
}

for (int i = 2; i < cost.size(); ++i)
g << (cost[i] < INT_MAX ? cost[i] : 0) << ' ';

return 0;
}``````