fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define pb push_back
  5. #define el '\n'
  6. const double pi=acos(-1);
  7. struct point{ll x, y;};
  8. struct bg {};
  9. ll sq(ll a){return (ll)a*a;}
  10. const ll sz=5000+10, MOD=1e9+7, inf=1e18;
  11.  
  12. ll n, k;
  13. vector<ll> g[sz];
  14. ll res=1e18;
  15. ll dd[sz];
  16. ll p[sz];
  17. ll sum;
  18.  
  19. void BFS(int i)
  20. {
  21. 	sum=k;
  22. 	queue<ll> q;
  23. 	for(int i=1;i<=n;i++)
  24. 	{
  25. 		p[i]=dd[i]=0;
  26. 	}
  27. 	q.push(i);
  28. 	dd[i]=1;
  29. 	p[i]=1;
  30. 	while(!q.empty())
  31. 	{
  32. 		int u=q.front();
  33. 		q.pop();
  34. 		for(auto v: g[u])
  35. 		{
  36. 			if(dd[v]==0)
  37. 			{
  38. 				dd[v]=1;
  39. 				p[v]=p[u]+1;
  40. 				sum+=p[v]*k;
  41. 				if(sum>res) return;
  42. 				q.push(v);
  43. 			}
  44. 		}
  45. 	}
  46. 	for(int i=1;i<=n;i++)
  47. 	{
  48. 		if(dd[i]==0)return;
  49. 	}
  50. 	res=sum;
  51. }
  52.  
  53. void doc()
  54. {
  55. 	cin>>n>>k;
  56. 	for(int i=1;i<=n;i++)
  57. 	{
  58. 		int s;
  59. 		cin>>s;
  60. 		while(s--)
  61. 		{
  62. 			ll x;
  63. 			cin>>x;
  64. 			g[x].pb(i);
  65. 		}
  66. 	}
  67. 	for(int i=1;i<=n;i++)
  68. 	{
  69. 		BFS(i);
  70. 	}
  71. 	cout<<res<<el;
  72. }
  73.  
  74. signed main()
  75. {
  76. 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  77. // 	freopen("test1.inp", "r", stdin);
  78. // 	freopen("test1.out", "w", stdout);
  79. 	doc();
  80.  
  81. 	return 0;
  82. }
Success #stdin #stdout 0.01s 5284KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
1000000000000000000
https://ideone.com/fJruJX
language:
C++14 (gcc 8.3)
created:
162 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!