fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define pu push
  6. #define ins insert
  7. #define fi first
  8. #define se second
  9. #define all(a) a.begin(),a.end()
  10. #define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  11. #define fu(x,a,b) for (auto x=a;x<=b;x++)
  12. #define fd(x,a,b) for (auto x=a;x>=b;x--)
  13. #define int ll
  14.  
  15. using namespace std;
  16. #pragma GCC optimize("Ofast")
  17. #pragma GCC optimize("unroll-loops")
  18. //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  19.  
  20. typedef pair<int, int> ii;
  21. const int N = 2000+5;
  22. const int mod = 2147483647;
  23. const int inf = 1e18;
  24. using cd = complex<double>;
  25. const long double PI = acos(-1);
  26. int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 
  27.  
  28. int n, s, d[N][N];
  29. vector<int> q[105];
  30. vector<ii> adj[N];
  31.  
  32. void floyd() 
  33. {
  34. 	for (int i = 1; i <= n; i++) 
  35. 	{
  36. 		for (int j = 1; j <= n; j++) 
  37. 		{
  38. 			for (int k = 1; k <= n; k++) 
  39. 			{
  40. 				d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
  41. 			}
  42. 		}
  43. 	}
  44. }
  45.  
  46. int dist[N];
  47.  
  48. void process(int s) 
  49. {
  50. 	for (int i = 1; i <= n; i++) 
  51. 	{
  52. 		dist[i] = d[s][i];
  53. 		if (dist[i] <= 100) q[dist[i]].pb(i);
  54. 	}
  55. 	for (int i = 0; i <= 100; i++) 
  56. 	{
  57. 		while (q[i].size())
  58. 		{
  59. 			int u = q[i].back();
  60. 			q[i].pop_back();
  61. 			if (dist[u] < i) continue;
  62. 			for (auto j : adj[u]) 
  63. 			{
  64. 				int w = j.fi, v = j.se;
  65. 				if (dist[u] + w > 100) break;
  66. 				if (dist[u] + w < dist[v]) 
  67. 				{
  68. 					dist[v] = i + w;
  69. 					q[i+w].pb(v);
  70. 				}
  71. 			}
  72. 		}
  73. 	}
  74. 	for (int i = 1; i <= n; i++) d[s][i] = dist[i];
  75. }
  76.  
  77. void solve()
  78. {
  79. 	cin>>n>>s;
  80. 	for (int i = 1; i <= n; i++) 
  81. 	{
  82. 		for (int j = 1; j <= n; j++) 
  83. 		{
  84. 			if (i != j) 
  85. 			{
  86. 				d[i][j] = s % 1000;
  87. 				adj[i].pb({d[i][j], j});
  88. 				s = (s * 16807) % mod;
  89. 			}
  90. 		}
  91. 	}
  92. 	if (n <= 500) floyd();
  93. 	else {
  94. 		for (int i = 1; i <= n; i++) sort(all(adj[i]));
  95. 		// for (int i = 1; i <= n; i++) {
  96. 		// 	for (auto j : adj[i]) cout<<j.fi<<" ";
  97. 		// 	cout<<endl;
  98. 		// }
  99. 		for (int i = 1; i <= n; i++) process(i);
  100. 	}
  101. 	int ans = 0;
  102. 	for (int i = 1; i <= n; i++) 
  103. 	{
  104. 		for (int j = 1; j <= n; j++) ans = (ans * 16807 + d[i][j]) % mod;
  105. 	}
  106. 	cout<<ans;
  107. }
  108.  
  109. signed main()
  110. {
  111. 	bruh
  112. 	freopen("floyd.in","r",stdin);
  113. 	freopen("floyd.out","w",stdout);
  114. 	int t = 1;
  115. 	// cin>>t;
  116. 	while (t--)
  117. 	{
  118. 		solve();
  119. 		cout<<"\n";
  120. 	}
  121. }
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5DlUOr
language:
C++ (gcc 8.3)
created:
4 days 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!