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