Advertisement
Guest User

Untitled

a guest
Jan 24th, 2020
121
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.57 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement