fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. queue <int> q;
  5. const int MAXN = 1e5 + 7;
  6. int n, m, k, ans;
  7. vector <int> save;
  8. vector <int> a[MAXN];
  9. ll d_u[MAXN], d_v[MAXN];
  10. void bfs(ll *dist, int s){
  11.     fill(dist + 1, dist + 1 + n, INT_MAX);
  12.     q.push(s);
  13.     dist[s] = 0;
  14.     while(!q.empty()){
  15.         int u = q.front();
  16.         q.pop();
  17.         for(auto v : a[u]){
  18.             if(dist[v] > dist[u] + 1){
  19.                 dist[v] = dist[u] + 1;
  20.                 q.push(v);
  21.             }
  22.         }
  23.     }
  24.     if(s == n)
  25.         for(auto x : save) if(d_v[x] <= d_u[n]) ans++;
  26.  
  27. }
  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++){
  36.         int x;
  37.         cin >> x;
  38.         save.push_back(x);
  39.     }
  40.     for(int i = 1; i <= m; i++){
  41.         int x, y;
  42.         cin >> x >> y;
  43.         a[x].push_back(y);
  44.         a[y].push_back(x);
  45.     }
  46.     bfs(d_u, 1);
  47.     bfs(d_v, n);
  48.     cout << ans;
  49. }
Success #stdin #stdout 0.01s 5904KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/mEp2FC
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!