Untitled

#include <iostream>
#include <vector>
#include <cassert>


class Priority_Queue {
private:

    std::vector<std::pair<int, int>> heap;

public:

    Priority_Queue() {}

    ~Priority_Queue() {}

    void AddDigit(std::pair<int, int> digit);

    void SiftDown(int num);

    std::pair<int, int> ExtractMax();

    bool empty() { return (heap.size() == 0) ? true : false; }
};


void Priority_Queue::AddDigit(std::pair<int, int> digit) {
    heap.push_back({ digit.first, - digit.second });
    int index = heap.size() - 1;
    if (heap.size() == 1) return;
    while (!index) {
        int parent = (index - 1) / 2;
        if (heap.at(parent).second >= digit.second) return;
        std::swap(heap.at(index), heap.at(parent));
        index = parent;
    }

}


void Priority_Queue::SiftDown(int num) {
    int  left{2 * num + 1 }, right{ 2 * num + 2 };

    int largest = num;

    if (left < heap.size() && heap.at(left) > heap.at(num))
        largest = left;

    if (right < heap.size() && heap.at(right) > heap.at(largest))
        largest = right;

    if (largest != num) {
        std::swap(heap.at(num), heap.at(largest));
        this->SiftDown(largest);
    }
}


std::pair<int, int> Priority_Queue::ExtractMax() {
    assert(!heap.empty());

    std::pair<int, int> result = heap.at(0);

    heap.at(0) = heap.at(heap.size() - 1);

    heap.resize(heap.size() - 1);

    if (!heap.empty())
        this->SiftDown(0);
    return { result.first, -result.second };
}


class Graph {
private:

    std::vector<std::vector<std::pair<int, int>>> data;

public:

    Graph(int N);

    ~Graph() {};

    void AddEdge(int from, int to, int time);

    int Deicstra(int from, int x);

};


Graph::Graph(int N) {
    for (int i = 0; i < N; ++i) {
        std::vector<std::pair<int, int>> tmp;
        data.push_back(tmp);
    }
}


void Graph::AddEdge(int from, int to, int time) {
    data.at(from).push_back(std::make_pair(to,time));
    data.at(to).push_back(std::make_pair(from,time));
}


int Graph::Deicstra(int from, int x) {
    int time;

    std::vector<int>  d(data.size(), 2000000);

    d.at(from) = 0;

    Priority_Queue q;

    q.AddDigit(std::make_pair(from, 0));

    while (!q.empty()) {
        std::pair<int, int> v = q.ExtractMax();
        if (v.second > d.at(v.first)) continue;
        for (size_t j = 0; j < data.at(v.first).size(); ++j) {
            int to = data.at(v.first).at(j).first;
            int len = data.at(v.first).at(j).second;
            if (d.at(v.first) + len < d.at(to)) {
                d.at(to) = d.at(v.first) + len;
                q.AddDigit(std::make_pair(to, d.at(to)));
            }
        }

    }

    time = d.at(x);
    return time;
}


int main() {

    int N, M, from, to;

    std::cin >> N >> M;

    Graph g(N);

    for (int i = 0; i < M; ++i) {
        int tmp1, tmp2, tmp3;
        std::cin >> tmp1 >> tmp2 >> tmp3;
        g.AddEdge(tmp1, tmp2, tmp3);
    }

    std::cin >> from >> to;

    std::cout << g.Deicstra(from, to) << std::endl;

    //system("pause");
    return 0;
}