fork download
copy 
  1.     #include<bits/stdc++.h>
  2.  
  3.     typedef long long int ll;
  4.     typedef long double ld;
  5.  
  6.     #define fast ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  7.     #define enddl '\n'
  8.     #define ff first
  9.     #define ss second
  10.     #define pb push_back
  11.     #define mp make_pair
  12.     #define pii pair<int,int>
  13.     #define full(a) a.begin(),a.end()
  14.     #define mem(a,x) memset(a,x,sizeof(a))
  15.  
  16.     const int MAXN = 2*1e5+5;
  17.     const int MOD = 1e9+7;
  18.  
  19.     using namespace std;
  20.  
  21.     vector<int> v[MAXN];
  22.     int dp[MAXN];
  23.     int s , n , m;
  24.  
  25.     int main() {
  26.     	cin >> s >> n >> m; 
  27.     	for(int i=0;i<MAXN;i++) dp[i] = 1e8;
  28.     	while(m--) {
  29.     		int x,y;
  30.     		cin >> x >> y;
  31.     		v[x].pb(y);
  32.     		v[y].pb(x);
  33.     	}
  34.     	dp[n] = 0;
  35.     	priority_queue<pii,vector<pii>,greater<pii> > q;
  36.     	q.push({0,n});
  37.     	while(!q.empty()) {
  38.     		pii x = q.top();
  39.     		q.pop();
  40.     		for(auto next : v[x.second]) {
  41.     			if(dp[next] > dp[x.second] + 1) {
  42.     				dp[next] = dp[x.second] + 1;
  43.     				q.push({dp[next] , next});
  44.     			}
  45.     		}
  46.     	} 
  47.     	map<int,int> m;
  48.     	for(int i=1;i<=s;i++) {
  49.     		m[dp[i]]++;
  50.     	}
  51.     	assert(m.size() > 0);
  52.     	auto hmm = m.rbegin();
  53.     	cout << hmm->second << endl;
  54.  
  55.     }
Success #stdin #stdout 0s 20712KB
comments (?)
stdin
copy 
3 5 4
1 5
2 4
3 4
5 4
stdout
copy 
2
https://ideone.com/VR70BP
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!