Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <algorithm>
- #include <set>
- #include <unordered_map>
- #include <queue>
- using namespace std;
- unordered_map<int, vector<int>> graph;
- long long find(const vector<int>& priorities, int start, int maxPriority){
- queue<pair<long long, pair<int, int>>> pq;
- //sum, index, inSearchFor
- set<int> inCurrSearch;
- int searching = 1;
- pq.push({0, {start, 1}});
- while(!pq.empty()){
- long long currSum = pq.front().first;
- int currIndex = pq.front().second.first;
- pq.pop();
- if(inCurrSearch.find(currIndex) != inCurrSearch.end())
- continue;
- inCurrSearch.insert(currIndex);
- if(priorities[currIndex] == searching){
- if(searching == maxPriority)
- return currSum;
- searching++;
- inCurrSearch.clear();
- while(!pq.empty())
- pq.pop();
- }
- for(int neigh : graph[currIndex]){
- if(priorities[neigh] > searching)
- continue;
- pq.push({currSum + 1, {neigh, searching}});
- }
- }
- return -1;
- }
- int main() {
- int n, m, a, b, p, k;
- cin >> n >> m;
- vector<int> priorities(n, 0);
- for(int i = 0; i < m; i++){
- cin >> a >> b;
- graph[a].push_back(b);
- graph[b].push_back(a);
- }
- cin >> p;
- int start = 0;
- for(int i = 1; i <= p; i++){
- cin >> a;
- if(i == 1)
- start = a;
- priorities[a] = i;
- }
- cin >> k;
- for(int i = 1; i <= k; i++){
- cin >> a;
- priorities[a] = p + 1;
- }
- cout << find(priorities, start, p);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment