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.                     int ans=q.front().second+1;
  25.                     while(!q.empty())
  26.                         q.pop();
  27.                     return ans;
  28.                 }
  29.                 if(sf[g[u][i]]&&!f)
  30.                     v.pb(mp(q.front().second+1,g[u][i]));
  31.                 q.push(mp(g[u][i],q.front().second+1));
  32.                 vis[g[u][i]]=true;
  33.             }
  34.         }
  35.         q.pop();
  36.     }
  37.     return 0;
  38. }
  39. int main(){
  40.     scanf("%d%d%d",&n,&m,&k);
  41.     for(int a,i=0;i<k;i++){
  42.         scanf("%d",&a);a--;
  43.         sf[a]=true;
  44.     }
  45.     for(int a,b,i=0;i<m;i++){
  46.         scanf("%d%d",&a,&b);
  47.         a--;b--;
  48.         g[a].pb(b);
  49.         g[b].pb(a);
  50.     }
  51.     bfs(false);
  52.     sort(v.begin(),v.end());
  53.     int mn=1e8;
  54.     pair<int,int> p={0,0};
  55.     for(int i=0;i<k-1;i++){
  56.         if(v[i+1].first-v[i].first<mn){
  57.             mn=v[i+1].first-v[i].first;
  58.             p=mp(v[i].second,v[i+1].second);
  59.         }
  60.     }
  61.     for(int i=0;i<n;i++)
  62.         vis[i]=false;
  63.     g[p.first].pb(p.second);
  64.     g[p.second].pb(p.first);
  65.     printf("%d",bfs(true));
  66.  
  67. }
  68.  
  69.  
  70.  
Success #stdin #stdout 0s 8420KB
comments (?)
stdin
copy 
5 4 2
2 4
1 2
2 3
3 4
4 5
stdout
copy 
3
https://ideone.com/XGMQux
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!