D_L3

Shortest tour

Jan 8th, 2024
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.07 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <climits>
  7. #include <set>
  8. #include <queue>
  9.  
  10. using namespace std;
  11.  
  12. struct Vertex {
  13. int index;
  14. int number = -1;
  15. vector<int> neighbours;
  16. bool isFinish = false;
  17.  
  18. Vertex(int index) : index(index) {}
  19.  
  20. void add(int neighbour) {
  21. neighbours.push_back(neighbour);
  22. }
  23. };
  24.  
  25. vector<Vertex*> vertexes;
  26.  
  27. int getLen(int start) {
  28. priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> next;
  29. //currLen, index, addedInSearchFor
  30. next.push({ 0, {start, 0} });
  31. set<int> inCurrSearch;
  32. int currSearch = 0;
  33. while (!next.empty()) {
  34. int currLen = next.top().first;
  35. int currIndex = next.top().second.first;
  36. next.pop();
  37. if (inCurrSearch.find(currIndex) != inCurrSearch.end())
  38. continue;
  39. inCurrSearch.insert(currIndex);
  40. if (vertexes[currIndex]->number == currSearch) {
  41. currSearch++;
  42. inCurrSearch.clear();
  43. if (vertexes[currIndex]->isFinish) {
  44. return currLen;
  45. }
  46. }
  47.  
  48. for (int neighbour : vertexes[currIndex]->neighbours) {
  49. if (vertexes[neighbour]->number <= currSearch)
  50. next.push({ currLen + 1, {neighbour, currSearch} });
  51. }
  52. while (!next.empty() && next.top().second.second < currSearch)
  53. next.pop();
  54. }
  55. return -1;
  56. }
  57.  
  58. int main() {
  59. int n, m, a, b, k, start;
  60. cin >> n >> m;
  61.  
  62. for (int i = 0; i < n; i++) {
  63. vertexes.push_back(new Vertex(i));
  64. }
  65.  
  66. for (int i = 0; i < m; i++) {
  67. cin >> a >> b;
  68. if (a == b)
  69. {
  70. continue;
  71. }
  72. vertexes[a]->add(b);
  73. }
  74.  
  75. cin >> k;
  76.  
  77. for (int i = 0; i < k; i++) {
  78. cin >> a;
  79. vertexes[a]->number = i;
  80. if (i == 0)
  81. start = a;
  82. }
  83. vertexes[a]->isFinish = true;
  84. cout << getLen(start);
  85. return 0;
  86. }
  87.  
Advertisement
Add Comment
Please, Sign In to add comment