fork download
copy 
  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
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
pops count is 960500
1000000000
https://ideone.com/CQz4XZ
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!