fork(1) download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <map>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <set>
  7. #define pb push_back
  8. #define mp make_pair
  9. using namespace std;
  10. string s;
  11. int n,m,k;
  12. bool sf[200010],vis[200010];
  13. vector<int> g[200010];
  14. vector<pair<int,int>>v;
  15. int bfs(bool f){
  16.     queue<pair<int,int>>q;
  17.     q.push(mp(0,0));
  18.     vis[0]=true;
  19.     while(!q.empty()){
  20.         int u=q.front().first;
  21.         for(int i=0;i<g[u].size();i++){
  22.             if(!vis[g[u][i]]){
  23.                 if(g[u][i]==n-1)
  24.                     return q.front().second+1;
  25.  
  26.                 if(sf[g[u][i]]&&!f)
  27.                     v.pb(mp(q.front().second+1,g[u][i]));
  28.                 q.push(mp(g[u][i],q.front().second+1));
  29.                 vis[g[u][i]]=true;
  30.             }
  31.         }
  32.         q.pop();
  33.     }
  34.     return 0;
  35. }
  36. int main(){
  37.     scanf("%d%d%d",&n,&m,&k);
  38.     for(int a,i=0;i<k;i++){
  39.         scanf("%d",&a);a--;
  40.         sf[a]=true;
  41.     }
  42.     for(int a,b,i=0;i<m;i++){
  43.         scanf("%d%d",&a,&b);
  44.         a--;b--;
  45.         g[a].pb(b);
  46.         g[b].pb(a);
  47.     }
  48.     bfs(false);
  49.     sort(v.begin(),v.end());
  50.     int mn=1e8;
  51.     pair<int,int> p={0,0};
  52.     for(int i=0;i<k-1;i++){
  53.         if(v[i+1].first-v[i].first<mn){
  54.             mn=v[i+1].first-v[i].first;
  55.             p=mp(v[i].second,v[i+1].second);
  56.         }
  57.     }
  58.     for(int i=0;i<n;i++)
  59.         vis[i]=false;
  60.     g[p.first].pb(p.second);
  61.     g[p.second].pb(p.first);
  62.     printf("%d",bfs(true));
  63.  
  64. }
  65.  
  66.  
  67.  
Success #stdin #stdout 0s 8456KB
comments (?)
stdin
copy 
5 5 3
1 3 5
1 2
2 3
3 4
3 5
2 4
stdout
copy 
2
https://ideone.com/VfOkHU
language:
C++14 (gcc 8.3)
created:
4 years 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!