fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. #define pii pair<int,int>
  5. const int mxn = 5e4 + 5;
  6. int n,m,s,cnt[mxn],ans;
  7. set<pair<int,int>> adj[mxn];
  8. void dijsktra(int s) {
  9.     int dist[mxn];
  10.     memset(dist,60,sizeof dist);
  11.     int oo = dist[0];
  12.     dist[s] = 0;
  13.     cnt[s] = 1;
  14.     priority_queue<pii,vector<pii>,greater<pii>> q;
  15.     q.push({0,s});
  16.     while(!q.empty()) {
  17.         auto mx = q.top();
  18.         q.pop();
  19.         int len = mx.first , u = mx.second;
  20.         if(len > dist[u]) continue;
  21.         for(auto v : adj[u]) {
  22.             if(dist[u] + v.second == dist[v.first]) cnt[v.first] += cnt[u];
  23.             else if(dist[u] + v.second < dist[v.first]) {
  24.                 dist[v.first] = dist[u] + v.second;
  25.                 cnt[v.first] = cnt[u];
  26.                 q.push({dist[v.first] , v.first});
  27.             }
  28.         }
  29.     }
  30.     for(int i = 1;i <= n;i++) {
  31.         if(dist[i] < oo && cnt[i] >= 2) ans ++;
  32.     }
  33.     cout << ans << '\n';
  34. }
  35. int32_t main() {
  36.     ios_base::sync_with_stdio(false);
  37.     cin.tie(NULL);
  38.     cin >> n >> m >> s;
  39.     for(int i = 0;i < m;i++) {
  40.         int u,v;
  41.         cin >> u >> v;
  42.         adj[u].insert({v,1});
  43.     }
  44.     dijsktra(s);
  45.     return 0;
  46. }
  47.  
Success #stdin #stdout 0.01s 6252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/mRtiFW
language:
C++14 (gcc 8.3)
created:
2 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!