fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int MAXN = 1e5 + 7;
  5. vector <int> a[MAXN];
  6. int n, m, save[MAXN], k, ans = INT_MAX;
  7. long long dist[MAXN];
  8. queue <int > q;
  9. vector <pair<int, int>> edge;
  10.  
  11. void bfs(int x, int y){
  12.     q.push(x), q.push(y);
  13.     fill(dist + 1, dist + 1 + n, INT_MAX);
  14.     dist[x] = dist[y] = 0;
  15.     while(!q.empty()){
  16.         int u = q.front();
  17.         q.pop();
  18.         for(auto v : a[u]){
  19.             if(dist[v] > dist[u] + 1){
  20.                 dist[v] = dist[u] + 1;
  21.                 q.push(v);            
  22.             }
  23.         }
  24.     }
  25.     int sum = 0;
  26.     for(int i = 1; i <= k; i++) sum += dist[save[i]];
  27.     ans = min(ans, sum);
  28. }
  29.  
  30. int main(){
  31.     ios_base::sync_with_stdio(0);
  32.     cout.tie(0);
  33.     cin.tie(0);
  34.     cin >> n >> m >> k;
  35.     for(int i = 1; i <= k; i++) cin >> save[i];
  36.     for(int i = 1; i <= m; i++){
  37.         int x, y;
  38.         cin >> x >> y;
  39.         a[x].push_back(y);
  40.         a[y].push_back(x);
  41.         edge.push_back({x, y});
  42.     }
  43.     for(auto [x, y] : edge) bfs(x, y);
  44.     cout << ans;
  45. }
Success #stdin #stdout 0.01s 5812KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2147483647
https://ideone.com/kECGzi
language:
C++14 (gcc 8.3)
created:
10 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!