fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3.  
  4.  
  5. using namespace std;
  6.  
  7. using ll   = long long;
  8. using ii   = pair   < int , int >;
  9. using i3   = pair   < int , ii  >;
  10. using li   = pair   < ll  , int >;
  11. using lii  = pair   < ll  , ii  >;
  12. using pll  = pair   < ll  , ll  >;
  13. using vi   = vector < int       >;
  14. using vl   = vector < ll        >;
  15. using vii  = vector < ii        >;
  16. using vpll = vector < pll       >;
  17. using vi3  = vector < i3        >;
  18. using vlii = vector < lii       >;
  19.  
  20.  
  21. const int N = 110;
  22. const ll INF = 1e17 + 7;
  23. const double eps = 1e-9 , PI = acos(-1);
  24.  
  25.  
  26.  
  27. int n , m , K;
  28. int mat[N][N];
  29. int dis[N][N];
  30. int ok[N];
  31.  
  32.  
  33. void solve(int testCase){
  34.  
  35.     scanf("%d %d %d" , &n , &m , &K);
  36.  
  37.     for(int i = 0 ; i < m ; i ++){
  38.             int u , v;
  39.             scanf("%d %d" , &u , &v);
  40.  
  41.             mat[u][v] = mat[v][u] = 1;
  42.     }
  43.  
  44.     for(int i = 0 ; i < n ; i ++){
  45.             for(int j = 0 ; j < n ; j ++){
  46.                     if(i != j){
  47.                             if(mat[i][j] == 0)dis[i][j] = 1e9;
  48.                             else dis[i][j] = mat[i][j];
  49.                     }
  50.                     else dis[i][j] = mat[i][j];
  51.             }
  52.     }
  53.  
  54.     for(int k = 0 ; k < n ; k ++){
  55.             for(int i = 0 ; i < n ; i ++){
  56.                     for(int j = 0 ; j < n ; j ++){
  57.                             dis[i][j] = min(dis[i][j] , dis[i][k] + dis[k][j]);
  58.                     }
  59.             }
  60.     }
  61.  
  62.     /*
  63.     cout << endl << "distances:\n";
  64.     for(int i = 0 ; i < n ; i ++){
  65.             for(int j = 0 ; j < n ;  j ++){
  66.                     cout << "dis " << i << " -> " << j << " = " << dis[i][j] << endl;
  67.             }
  68.     }
  69.     cout << endl;
  70.     */
  71.  
  72.     for(int i = 0 ; i < n ; i ++){
  73.             for(int j = 0 ; j < n ; j ++){
  74.                     bool getOut = 0;
  75.                     for(int k = 0 ; k < n ; k ++){
  76.  
  77.                             int dis2 = dis[i][j] + dis[j][k] + dis[k][i];
  78.  
  79.                             //cout << i << " -> " << j << " -> " << k << " -> " << i << " = " << dis2 << endl;
  80.  
  81.                             if( (j != i) ){
  82.                                     //cout << K << " " << dis2 << endl;
  83.                                     if(((K - dis2) >= 0) && ((K - dis2)%2 == 0)){
  84.                                             ok[i] = 1;
  85.                                             getOut = 1;
  86.                                             //cout << i << " " << j << " " << k << endl;
  87.                                             //cout << "dis = " << dis2 << endl;
  88.                                             break;
  89.                                     }
  90.                             }
  91.                     }
  92.                     if(getOut)break;
  93.             }
  94.     }
  95.  
  96.     int ans = 0;
  97.     for(int i = 0 ; i < n ; i ++){
  98.             ans += ok[i];
  99.     }
  100.  
  101.     printf("%d\n" , ans);
  102.  
  103.  
  104. }
  105.  
  106. main(){
  107.  
  108.     int t = 1;
  109.     scanf("%d" , &t);
  110.  
  111.     for(int testCase = 1 ; testCase <= t ; testCase ++){
  112.             solve(testCase);
  113.             memset(ok , 0 , sizeof ok);
  114.             memset(mat , 0 , sizeof mat);
  115.             memset(dis , 0 , sizeof dis);
  116.     }
  117.  
  118.     return 0;
  119. }
  120.  
  121. /*
  122. 4 4 3
  123. 0 1
  124. 1 2
  125. 2 3
  126. 3 3
  127.  
  128. */
  129.  
Success #stdin #stdout 0s 4464KB
comments (?)
stdin
copy 
1
4 4 3
0 1
1 2
2 3
3 3
stdout
copy 
2
https://ideone.com/D4MjzN
language:
C++14 (gcc 8.3)
created:
4 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!