Dijkstra's

#include <iostream>
#include <vector>
#include <queue>
#include <utility>


using namespace std;
using vvi = vector<vector<int>>;

const int INF = 1e9;
template <class T>
class Heap
{
private:
    T* arr;
    int size;
    int maxSize;

    void FilterDown(int cur)
    {
        int curChild = 2 * cur + 1;

        while (cur < size)
        {
            curChild = ((curChild + 1 < size) && arr[curChild] < arr[curChild + 1]) ? curChild + 1 : curChild;
            if (arr[curChild] <= arr[cur]) break;

            swap(arr[cur], arr[curChild]);
            cur = curChild;
            curChild = 2 * cur + 1;

        }
    }

    void FilterUp(int cur)
    {
        int parent = (cur - 1) / 2;

        while (cur && arr[cur] >= arr[parent])
        {
            swap(arr[cur], arr[parent]);
            cur = parent;
            parent = (cur - 1) / 2;
        }
    }

    void HeapBuild()
    {
        int cur = (size - 2) / 2;

        while (cur >= 0)
        {
            FilterDown(cur);
            cur--;
        }

    }

public:

    Heap(int _maxSize = 256)
    {
        maxSize = _maxSize;
        size = 0;
        arr = new T[maxSize];

        if (arr == 0) throw "MemoryAllocError";
    }

    Heap(int _size, int _maxSize = 256)
    {
        size = _size;
        maxSize = _maxSize;
        arr = new T[maxSize];

        if (arr == 0) throw "MemoryAllocError";
    }

    Heap(T* _arr, int _size, int _maxSize = 256)
    {
        if (_arr == nullptr) throw "Nullptr";

        size = _size;
        maxSize = _maxSize;
        arr = new T[maxSize];

        if (arr == 0) throw "MemoryAllocError";

        for (int i = 0; i < size; ++i)
            Heap<T>::arr[i] = _arr[i];

        HeapBuild();


    }

    Heap(const Heap<T>& H)
    {
        if (H.arr == nullptr) throw "Nullptr";

        size = H.size;
        maxSize = H.maxSize;
        arr = new T[maxSize];

        if (arr == 0) throw "MemoryAllocError";

        for (int i = 0; i < size; ++i)
            this->arr[i] = H.arr[i];


        HeapBuild();
    }

    void push(const T& key)
    {

        if (!size)
        {
            arr = new T[maxSize];
            if (arr == 0) throw "MemoryAllocError";
        }

        if (size == maxSize)
        {
            T* arrBuff = arr;
            arr = new T[maxSize * 2];

            if (arr == 0) throw "MemoryAllocError";

            for (int i = 0; i < size; ++i)
                arr[i] = arrBuff[i];

            delete[] arrBuff;
        }

        size++;
        arr[size - 1] = key;
        FilterUp(size - 1);
    }

    void pop()
    {
        arr[0] = arr[size - 1];
        size--;

        FilterDown(0);
    }

    T top() const
    {
        return arr[0];
    }

    bool empty() const
    {
        return (size == 0);
    }

    void print() const
    {
        for (int i = 0; i < size; ++i)
            cout << arr[i] << " ";
        cout << '\n';
    }

    ~Heap()
    {
        delete[] arr;
    }
};

vector<int> dijkstra_with_vector(vvi graph, int start)
{
    int n = graph.size();
    vector<int> dist(n, INF);
    vector<bool> visited(n, 0);
    vector<int> q = { start };

    dist[start] = 0;

    while (!q.empty())
    {
        int u = q.back();
        q.pop_back();

        if (visited[u]) continue;
        visited[u] = 1;

        for (int i = 0; i < graph[u].size(); ++i)
        {
            if (graph[u][i] != 0 && (dist[i] == INF || dist[i] > dist[u] + graph[u][i]))
            {
                dist[i] = dist[u] + graph[u][i];
                q.push_back(i);
            }
        }
    }

    return dist;
}

vector<int> dijkstra_with_queue(vvi graph, int start)
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    vector<int> dist(graph.size(), INF);
    vector<bool> visited(graph.size(), 0);

    q.push({0, start});
    dist[start] = 0;


    while (!q.empty())
    {
        int u = q.top().second;
        int dist_u = q.top().first;
        q.pop();

        if (visited[u]) continue;
        visited[u] = 1;

        for (int i = 0; i < graph[u].size(); ++i)
        {
            if (graph[u][i] != 0 && dist[i] > dist_u + graph[u][i])
            {
                dist[i] = dist_u + graph[u][i];
                q.push({ dist[i], i });
            }
        }
    }
    return dist;
}

vector<int> dijkstra_with_heap(vvi graph, int start)
{
    Heap<pair<int,int>> heap;
    vector<int> dist(graph.size(), INF);
    vector<bool> visited(graph.size(), 0);

    dist[start] = 0;
    heap.push({0, start});

    while (!heap.empty())
    {
        int u = heap.top().second;
        int dist_u = heap.top().first;
        heap.pop();

        if (visited[u]) continue;
        visited[u] = 1;

        for (int i = 0; i < graph[u].size(); ++i)
        {
            if (graph[u][i] != 0 &&  dist[i] > dist_u + graph[u][i])
            {
                dist[i] = dist_u + graph[u][i];
                heap.push({ dist[i], i });

            }
        }

    }

    return dist;
}

int main()
{
    int n;
    cin >> n;

    int s, k;
    cin >> s >> k;
    s--; k--;

    vector<vector<int>> graph(n, vector<int>(n, 0));

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> graph[i][j];


    vector<int> dist = dijkstra_with_vector(graph, s);
    vector<int> dist2 = dijkstra_with_queue(graph, s);
    vector<int> dist3 = dijkstra_with_heap(graph, s);

    cout << dist[k] << ' ' << dist2[k] << ' ' << dist3[k];

    return 0;
}