Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
RAW Paste Data