fork download
  1. #pragma GCC optimize ("O3")
  2. #pragma GCC target ("sse4")
  3.  
  4. #include <bits/stdc++.h>
  5. #include <ext/pb_ds/tree_policy.hpp>
  6. #include <ext/pb_ds/assoc_container.hpp>
  7.  
  8. using namespace std;
  9. using namespace __gnu_pbds;
  10.  
  11. typedef long long ll;
  12. typedef long double ld;
  13. typedef complex<ld> cd;
  14.  
  15. typedef pair<int, int> pi;
  16. typedef pair<ll,ll> pl;
  17. typedef pair<ld,ld> pd;
  18.  
  19. typedef vector<int> vi;
  20. typedef vector<ld> vd;
  21. typedef vector<ll> vl;
  22. typedef vector<pi> vpi;
  23. typedef vector<pl> vpl;
  24. typedef vector<cd> vcd;
  25.  
  26.  
  27. template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
  28.  
  29. #define FOR(i, a, b) for (int i=a; i<(b); i++)
  30. #define F0R(i, a) for (int i=0; i<(a); i++)
  31. #define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
  32. #define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
  33.  
  34. #define sz(x) (int)(x).size()
  35. #define mp make_pair
  36. #define pb push_back
  37. #define f first
  38. #define s second
  39. #define lb lower_bound
  40. #define ub upper_bound
  41. #define all(x) x.begin(), x.end()
  42. #define shandom_ruffle random_shuffle
  43.  
  44. const int MOD = 1000000007;
  45. const ll INF = 1e18;
  46. const int MX = 100001; //check the limits, dummy
  47.  
  48. struct data {
  49. ll weight; int start, last, index;
  50. data(ll w, int S, int L, int I) {
  51. weight = w; start = S; last = L; index = I;
  52. }
  53. bool operator<(data other) const
  54. {
  55. return weight > other.weight;
  56. }
  57. };
  58.  
  59.  
  60. int main() {
  61. ios_base::sync_with_stdio(0); cin.tie(0);
  62.  
  63. int N, M, K; //cin >> N >> M >> K;
  64. N = 100;
  65. M = 4950;
  66. K = 4852;
  67. vector<vpl> graph(N);
  68. /*F0R(i, M) {
  69.   ll A, B, C; cin >> A >> B >> C; A--; B--;
  70.   graph[A].pb(mp(C, B));
  71.   graph[B].pb(mp(C, A));
  72.   }*/
  73. for(int i=0; i<=N-3; i++) {
  74. for(int j=i+1; j<=N-2; j++) {
  75. graph[i].pb(mp(1, j));
  76. graph[j].pb(mp(1, i));
  77. }
  78. }
  79. for(int i=0; i<=N-2; i++) {
  80. graph[i].pb(mp(1000000000, N-1));
  81. graph[N-1].pb(mp(1000000000, i));
  82. }
  83.  
  84. F0R(i, N) {
  85. sort(all(graph[i]));
  86. }
  87.  
  88. priority_queue<data> pq; //-weight, edge index, start, next-to-last.
  89. K *= 2;
  90. set<pl> visited;
  91. F0R(i, N) {
  92. pq.push(data(graph[i][0].f, i, i, 0));
  93. visited.insert(mp(i, i));
  94. }
  95. int pops_count = 0;
  96. while (!pq.empty()) {
  97. data cur = pq.top();
  98. pq.pop();
  99. pops_count++;
  100. int nxt = graph[cur.last][cur.index].s;
  101. if (!visited.count(mp(cur.start, graph[cur.last][cur.index].s))) {
  102. visited.insert(mp(cur.start, graph[cur.last][cur.index].s));
  103. //cout << cur.start << " " << nxt << " " << cur.weight << endl;
  104. K--;
  105. if (K == 0) {
  106. cout << "pops count is " << pops_count << endl;
  107. cout << cur.weight << endl; return 0;
  108. }
  109. pq.push(data(cur.weight + graph[nxt][0].f, cur.start, nxt, 0));
  110. }
  111. if (cur.index + 1 < sz(graph[cur.last])) {
  112. pq.push(data(cur.weight - graph[cur.last][cur.index].f + graph[cur.last][cur.index + 1].f, cur.start, cur.last, cur.index + 1));
  113. }
  114.  
  115. }
  116.  
  117. return 0;
  118. }
  119.  
  120. // read the question correctly (ll vs int)
  121. // template by bqi343
Success #stdin #stdout 0.08s 4476KB
stdin
Standard input is empty
stdout
pops count is 960500
1000000000