• API
• FAQ
• Tools
• Archive
SHARE
TWEET

# Untitled

a guest Jan 24th, 2020 89 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <cmath>
2. #include <cstdio>
3. #include <vector>
4. #include <iostream>
5. #include <queue>
6. #include <algorithm>
7. using namespace std;
8. vector<vector<int>> graph;
9. vector<int> path;
10. int distance(int source ,int target){
11.     vector<bool> used;
12.     used.resize(graph.size());
13.     queue<pair<int,int>> q;
14.     used[path[source]] = true;
15.     q.push({path[source], 0});
16.     for(int i=source;i<path.size();i++){
17.         used[path[i]] = true;
18.     }
19.     int finalDistance = -1;
20.     bool stop = false;
21.     while(!q.empty()){
22.         if(stop) break;
23.         auto current = q.front();
24.         q.pop();
25.         int distance = current.second;
26.         int element = current.first;
27.         for(auto n: graph[element]){
28.             if(n == path[target]){
29.                 finalDistance = distance+1;
30.                 stop = true;
31.                 break;
32.             }
33.             if(!used[n]){
34.                 used[n] = true;
35.                 q.push({n, distance+1});
36.             }
37.         }
38.     }
39.     return finalDistance;
40. }
41. int main() {
42.     int n,m;
43.     scanf("%d%d", &n, &m);
44.     int u,v;
45.     graph.resize(n);
46.     for(int i=0;i<m;i++){
47.         scanf("%d%d", &u, &v);
48.         graph[u].push_back(v);
49.     }
50.     int k;
51.     scanf("%d", &k);
52.     path.resize(k);
53.     for(int i=0;i<k;i++){
54.         scanf("%d", &path[i]);
55.     }
56.     int sum = 0;
57.     int currentD = 0;
58.     for(int i=0;i<k-1;i++){
59.         currentD = distance(i,i+1);
60.         if(currentD==-1){
61.             cout<<-1;
62.             return 0;
63.         }
64.         sum+=currentD;
65.     }
66.     cout<<sum;
67.     return 0;
68. }
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.
Top