Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <cmath>
- #include <cstdio>
- #include <vector>
- #include <iostream>
- #include <queue>
- #include <algorithm>
- using namespace std;
- vector<vector<int>> graph;
- vector<int> path;
- int distance(int source ,int target){
- vector<bool> used;
- used.resize(graph.size());
- queue<pair<int,int>> q;
- used[path[source]] = true;
- q.push({path[source], 0});
- for(int i=source;i<path.size();i++){
- used[path[i]] = true;
- }
- int finalDistance = -1;
- bool stop = false;
- while(!q.empty()){
- if(stop) break;
- auto current = q.front();
- q.pop();
- int distance = current.second;
- int element = current.first;
- for(auto n: graph[element]){
- if(n == path[target]){
- finalDistance = distance+1;
- stop = true;
- break;
- }
- if(!used[n]){
- used[n] = true;
- q.push({n, distance+1});
- }
- }
- }
- return finalDistance;
- }
- int main() {
- int n,m;
- scanf("%d%d", &n, &m);
- int u,v;
- graph.resize(n);
- for(int i=0;i<m;i++){
- scanf("%d%d", &u, &v);
- graph[u].push_back(v);
- }
- int k;
- scanf("%d", &k);
- path.resize(k);
- for(int i=0;i<k;i++){
- scanf("%d", &path[i]);
- }
- int sum = 0;
- int currentD = 0;
- for(int i=0;i<k-1;i++){
- currentD = distance(i,i+1);
- if(currentD==-1){
- cout<<-1;
- return 0;
- }
- sum+=currentD;
- }
- cout<<sum;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement