fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll int
  4. const int inf = INT_MAX;
  5. const int MAXN = 1e5 + 7;
  6. queue <int> q;
  7. vector <int>a[MAXN];
  8. int n, m, s, t, d_u[MAXN], d_v[MAXN], ans;
  9.  
  10. void bfs(int *dist, int s){
  11.     q.push(s);
  12.     fill(dist + 1, dist + 1 + n, inf);
  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. }
  25.  
  26.  
  27. int main(){
  28.     ios_base::sync_with_stdio(0);
  29.     cout.tie(0);
  30.     cin.tie(0);
  31.     cin >> n >> m >> s >> t;
  32.     for(int i = 1; i <= m; i++){
  33.         int x, y;
  34.         cin >> x >> y;
  35.         a[x].push_back(y);
  36.         a[y].push_back(x);
  37.     }
  38.     bfs(d_u, s);
  39.     bfs(d_v, t);
  40.     for(int i = 1; i <= n; i++) if(d_u[i] <= d_v[i]) ans++;
  41.     cout << ans;
  42. }
Success #stdin #stdout 0.01s 5916KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/pcdIW1
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!