fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define dandelion ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  4. #define FOR(i,a,b) for(long long i=a;i<=b;i++)
  5. #define FOD(i,a,b) for(long long i=a;i>=b;i--)
  6. #define pb push_back
  7.  
  8. using namespace std;
  9. const int N = 1e6+5;
  10.  
  11. int n,k;
  12. vector<int> g[N];
  13. ll f[N] = {};
  14. bool dd[N] = {};
  15. ll res = LLONG_MAX;
  16.  
  17. void bfs(int u){  //dinh cay
  18. 	ll tmp = 0;
  19. 	f[u] = 1;   //tang lop
  20. 	int cnt = 1;   //sl nhan vien 
  21. 	tmp += f[u]*k;    //luong cua dinh cay la thap nhat
  22.  
  23. 	queue<int> q;
  24. 	q.push(u);
  25. 	dd[u] = true;
  26.  
  27. 	while(!q.empty()){
  28. 		int v = q.front();
  29. 		q.pop();
  30. 		for(int x : g[v]){  //nv ben duoi
  31. 			if(dd[x] == false){
  32. 				dd[x] = true;
  33. 				cnt++;
  34. 				f[x] = f[v] + 1;
  35. 				tmp += f[x]*k;
  36. 				if(tmp > res) return;  //ko toi uu thi bo di
  37. 				if(cnt == n) res = min(res,tmp);  //nv du
  38. 				q.push(x);
  39. 			}
  40. 		}
  41. 	}
  42. }
  43.  
  44. int main(){
  45. 	dandelion
  46.  
  47. 	cin>>n>>k;
  48. 	FOR(i,1,n){
  49. 		int q;
  50. 		cin>>q;
  51. 		while(q--){
  52. 			int x;
  53. 			cin>>x;
  54. 			g[x].pb(i);
  55. 		}
  56. 	}
  57.  
  58. 	FOR(i,1,n){
  59. 		fill(f+1,f+n+1,0);
  60. 		fill(dd+1,dd+n+1,false);
  61. 		bfs(i);
  62. 	}
  63.  
  64. 	cout<<res;
  65.  
  66. 	return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 28852KB
comments ()
stdin 
Standard input is empty
stdout 
9223372036854775807
https://ideone.com/FzMQUA
language:
C++14 (gcc 8.3)
created:
138 days 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!