fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const long long MaxK = 1e3+5, MaxM = 3e3+5;
  4. long long n,m,k,ans=LLONG_MAX,p[MaxK], dis[MaxK][MaxK], visited[MaxK];
  5. vector<long long> arr[MaxK];
  6. pair<long long, long long> pr[MaxM];
  7. void bfs(long long x, long long visited[], vector<long long> arr[])
  8. {
  9.     for (long long i=1; i<=n; i++)
  10.     {
  11.         visited[i]=false;
  12.     }
  13.     queue<long long> qu;
  14.     qu.push(x);
  15.     visited[x]=true;
  16.     while(!qu.empty())
  17.     {
  18.         long long u = qu.front();
  19.         qu.pop();
  20.         for(long long v : arr[u])
  21.         {
  22.             if(!visited[v])
  23.             {
  24.                 dis[x][v]=dis[x][u]+1;
  25.                 visited[v]=true;
  26.                 qu.push(v);
  27.             }
  28.         }
  29.     }
  30. }
  31. void input()
  32. {
  33.     cin >> n >> m >> k;
  34.     for (long long i=1; i<=k; i++)
  35.     {
  36.         cin>> p[i];
  37.     }
  38.     for (long long i=1; i<=m; i++)
  39.     {
  40.         long long u,v;
  41.         cin >> u >> v;
  42.         arr[u].push_back(v);
  43.         arr[v].push_back(u);
  44.         pr[i]={u,v};
  45.     }
  46. }
  47. void solve()
  48. {
  49.     for (long long i=1; i<=n; i++)
  50.     {
  51.         bfs(i,visited,arr);
  52.     }
  53.     for (long long i=1; i<=m; i++)
  54.     {
  55.         long long u = pr[i].first, v=pr[i].second, cnt= 0;
  56.         for (long long i=1; i<=k; i++)
  57.         {
  58.             cnt += min(dis[u][p[i]],dis[v][p[i]]);
  59.         }
  60.         ans=min(ans,cnt);
  61.     }
  62.     cout << ans;
  63. }
  64. int main()
  65. {
  66.     ios_base::sync_with_stdio(0);
  67.     cin.tie(0);
  68.     input();
  69.     solve();
  70.     return 0;
  71. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
9223372036854775807
https://ideone.com/2eQb0R
language:
C++14 (gcc 8.3)
created:
3 hours 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!