Guest User

Untitled

a guest
Dec 14th, 2019
115
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