D_L3

Най-кратка поредица от пътища

Jan 26th, 2024
850
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.78 KB | None | 0 0
  1. #include <cmath>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <iostream>
  5. #include <algorithm>
  6. #include <set>
  7. #include <unordered_map>
  8. #include <queue>
  9.  
  10.  
  11. using namespace std;
  12.  
  13. unordered_map<int, vector<int>> graph;
  14.  
  15. long long find(const vector<int>& priorities, int start, int maxPriority){
  16.     queue<pair<long long, pair<int, int>>> pq;
  17.     //sum, index, inSearchFor
  18.     set<int> inCurrSearch;
  19.     int searching = 1;
  20.     pq.push({0, {start, 1}});
  21.    
  22.     while(!pq.empty()){
  23.         long long currSum = pq.front().first;
  24.         int currIndex = pq.front().second.first;
  25.         pq.pop();
  26.  
  27.         if(inCurrSearch.find(currIndex) != inCurrSearch.end())
  28.             continue;
  29.         inCurrSearch.insert(currIndex);
  30.        
  31.         if(priorities[currIndex] == searching){
  32.             if(searching == maxPriority)
  33.                 return currSum;
  34.             searching++;
  35.             inCurrSearch.clear();
  36.             while(!pq.empty())
  37.                 pq.pop();
  38.         }
  39.        
  40.         for(int neigh : graph[currIndex]){
  41.             if(priorities[neigh] > searching)
  42.                 continue;
  43.             pq.push({currSum + 1, {neigh, searching}});
  44.         }
  45.        
  46.        
  47.     }
  48.     return -1;
  49. }
  50.  
  51. int main() {
  52.     int n, m, a, b, p, k;
  53.     cin >> n >> m;
  54.     vector<int> priorities(n, 0);
  55.  
  56.     for(int i = 0; i < m; i++){
  57.         cin >> a >> b;
  58.         graph[a].push_back(b);
  59.         graph[b].push_back(a);
  60.     }
  61.     cin >> p;
  62.     int start = 0;
  63.    
  64.     for(int i = 1; i <= p; i++){
  65.         cin >> a;
  66.         if(i == 1)
  67.             start = a;
  68.         priorities[a] = i;
  69.     }
  70.    
  71.     cin >> k;
  72.     for(int i = 1; i <= k; i++){
  73.         cin >> a;
  74.         priorities[a] = p + 1;
  75.     }
  76.     cout << find(priorities, start, p);
  77.     return 0;
  78. }
  79.  
Advertisement
Add Comment
Please, Sign In to add comment