SHARE
TWEET

Untitled

a guest Dec 14th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <cassert>
  4.  
  5.  
  6. class Priority_Queue {
  7. private:
  8.  
  9.     std::vector<std::pair<int, int>> heap;
  10.  
  11. public:
  12.  
  13.     Priority_Queue() {}
  14.  
  15.     ~Priority_Queue() {}
  16.  
  17.     void AddDigit(std::pair<int, int> digit);
  18.  
  19.     void SiftDown(int num);
  20.  
  21.     std::pair<int, int> ExtractMax();
  22.  
  23.     bool empty() { return (heap.size() == 0) ? true : false; }
  24. };
  25.  
  26.  
  27. void Priority_Queue::AddDigit(std::pair<int, int> digit) {
  28.     heap.push_back({ digit.first, - digit.second });
  29.     int index = heap.size() - 1;
  30.     if (heap.size() == 1) return;
  31.     while (!index) {
  32.         int parent = (index - 1) / 2;
  33.         if (heap.at(parent).second >= digit.second) return;
  34.         std::swap(heap.at(index), heap.at(parent));
  35.         index = parent;
  36.     }
  37.  
  38. }
  39.  
  40.  
  41. void Priority_Queue::SiftDown(int num) {
  42.     int  left{2 * num + 1 }, right{ 2 * num + 2 };
  43.  
  44.     int largest = num;
  45.  
  46.     if (left < heap.size() && heap.at(left) > heap.at(num))
  47.         largest = left;
  48.  
  49.     if (right < heap.size() && heap.at(right) > heap.at(largest))
  50.         largest = right;
  51.  
  52.     if (largest != num) {
  53.         std::swap(heap.at(num), heap.at(largest));
  54.         this->SiftDown(largest);
  55.     }
  56. }
  57.  
  58.  
  59. std::pair<int, int> Priority_Queue::ExtractMax() {
  60.     assert(!heap.empty());
  61.  
  62.     std::pair<int, int> result = heap.at(0);
  63.  
  64.     heap.at(0) = heap.at(heap.size() - 1);
  65.  
  66.     heap.resize(heap.size() - 1);
  67.  
  68.     if (!heap.empty())
  69.         this->SiftDown(0);
  70.     return { result.first, -result.second };
  71. }
  72.  
  73.  
  74.  
  75. class Graph {
  76. private:
  77.  
  78.     std::vector<std::vector<std::pair<int, int>>> data;
  79.  
  80. public:
  81.  
  82.     Graph(int N);
  83.  
  84.     ~Graph() {};
  85.  
  86.     void AddEdge(int from, int to, int time);
  87.  
  88.     int Deicstra(int from, int x);
  89.  
  90. };
  91.  
  92.  
  93. Graph::Graph(int N) {
  94.     for (int i = 0; i < N; ++i) {
  95.         std::vector<std::pair<int, int>> tmp;
  96.         data.push_back(tmp);
  97.     }
  98. }
  99.  
  100.  
  101. void Graph::AddEdge(int from, int to, int time) {
  102.     data.at(from).push_back(std::make_pair(to,time));
  103.     data.at(to).push_back(std::make_pair(from,time));
  104. }
  105.  
  106.  
  107. int Graph::Deicstra(int from, int x) {
  108.     int time;
  109.  
  110.     std::vector<int>  d(data.size(), 2000000);
  111.  
  112.     d.at(from) = 0;
  113.  
  114.     Priority_Queue q;
  115.  
  116.     q.AddDigit(std::make_pair(from, 0));
  117.  
  118.     while (!q.empty()) {
  119.         std::pair<int, int> v = q.ExtractMax();
  120.         if (v.second > d.at(v.first)) continue;
  121.         for (size_t j = 0; j < data.at(v.first).size(); ++j) {
  122.             int to = data.at(v.first).at(j).first;
  123.             int len = data.at(v.first).at(j).second;
  124.             if (d.at(v.first) + len < d.at(to)) {
  125.                 d.at(to) = d.at(v.first) + len;
  126.                 q.AddDigit(std::make_pair(to, d.at(to)));
  127.             }
  128.         }
  129.  
  130.     }
  131.  
  132.     time = d.at(x);
  133.     return time;
  134. }
  135.  
  136.  
  137. int main() {
  138.  
  139.     int N, M, from, to;
  140.  
  141.     std::cin >> N >> M;
  142.    
  143.     Graph g(N);
  144.  
  145.     for (int i = 0; i < M; ++i) {
  146.         int tmp1, tmp2, tmp3;
  147.         std::cin >> tmp1 >> tmp2 >> tmp3;
  148.         g.AddEdge(tmp1, tmp2, tmp3);
  149.     }
  150.  
  151.     std::cin >> from >> to;
  152.  
  153.     std::cout << g.Deicstra(from, to) << std::endl;
  154.  
  155.     //system("pause");
  156.     return 0;
  157. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top