Advertisement
leminhkt

70

Jul 25th, 2020
78
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.92 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. vector<int> edge[1001];
  6. bool visited[1001];
  7.  
  8.  
  9. int BFS(int s, int t){
  10.     queue<pair<int, int>> q;
  11.     q.push({s, 0});
  12.     memset(visited, false, sizeof(visited));
  13.     while(!q.empty()){
  14.         int u = q.front().first, u_len = q.front().second;
  15.         visited[u] = true;
  16.         if(u == t)
  17.             return u_len;
  18.         q.pop();
  19.         for(int i : edge[u])
  20.             if(!visited[i])
  21.                 q.push({i, u_len + 1});
  22.     }
  23. }
  24.  
  25.  
  26. int main(){
  27.     {
  28.         freopen("TOUR.INP", "r", stdin);
  29.         freopen("TOUR.OUT", "w", stdout);
  30.     } //file
  31.  
  32.  
  33.     int n, k, m, result = 0;
  34.     {
  35.         cin >> n >> k >> m;
  36.     }
  37.  
  38.  
  39.     vector<int> stop(k + 2);
  40.     {
  41.         for(int i = 0; i <= k; ++i)
  42.             cin >> stop[i];
  43.         stop[k + 1] = stop[0];
  44.     }
  45.  
  46.  
  47.     {
  48.         int u, v;
  49.         for(int i = 0; i < m; ++i)
  50.             cin >> u >> v,
  51.             edge[u].push_back(v),
  52.             edge[v].push_back(u);
  53.     }
  54.  
  55.  
  56.     {
  57.         for(int i = 0; i <= k; ++i)
  58.             result += BFS(stop[i], stop[i + 1]);
  59.         cout << result;
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement