fork download
copy 
  1. /// no time to waste
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. #define ll long long
  5. #define ull unsigned ll
  6. #define ld long double
  7. #define eb emplace_back
  8. #define ef emplace_front
  9. #define pii pair <int, int>
  10. #define pli pair <ll, int>
  11. #define pll pair <ll, ll>
  12. #define pci pair <char, int>
  13. #define pil pair <int, ll>
  14. #define pic pair <int, char>
  15. #define pib pair <int, bool>
  16. #define pbi pair <bool, int>
  17. #define pcc pair <char, char>
  18. #define fi first
  19. #define se second
  20. #define all(ac) ac.begin(), ac.end()
  21. #define MASK(x) (1 << (x))
  22. #define ub(i, j) (((i) >> (j)) & 1)
  23. #define FBIT(x) (MASK(x) - 1)
  24. #define FLIP(x, y) (FBIT(x) ^ (y))
  25. #define bit_count(x) (int) (__builtin_popcount(x))
  26. #define bit_countll(x) (int) (__builtin_popcountll(x))
  27. #define ii make_pair
  28. #define int128 __int128_t
  29. #define SZ(x) ((int) x.size())
  30. #define UNIQUE(IV) (sort(all(IV)), IV.erase(unique(all(IV)), IV.end()))
  31. #define multi 0
  32.  
  33. struct DSU {
  34.     int n;
  35.     vector <int> lab;
  36.  
  37.     DSU(int n = 0): n(n), lab(n + 1, -1) {}
  38.  
  39.     int find(int u) {
  40.         return lab[u] < 0 ? u : lab[u] = find(lab[u]);
  41.     }
  42.  
  43.     bool join(int a, int b) {
  44.         a = find(a);
  45.         b = find(b);
  46.  
  47.         if(a != b) {
  48.             if(lab[a] > lab[b]) swap(a, b);
  49.             lab[a] += lab[b];
  50.             lab[b] = a;
  51.  
  52.             return 1;
  53.         }
  54.  
  55.         return 0;
  56.     }
  57. } dsu;
  58.  
  59. const int MX = 1004;
  60. int n, m, k;
  61. ll dis[MASK(12)];
  62.  
  63. struct edge {
  64.     int u, v, w;
  65.     edge(int u = 0, int v = 0, int w = 0): u(u), v(v), w(w) {}
  66.  
  67.     bool operator <(const edge &other) const {
  68.         return w < other.w;
  69.     }
  70. } e[MX];
  71.  
  72. bool ok(int u, int mask) {
  73.     return u < k || ub(mask, u - k);
  74. }
  75.  
  76. int head[MX], nxt[MX << 1], ecnt;
  77. pii to[MX << 1];
  78.  
  79. void add_edge(int x, int y, int w) {
  80.     to[++ecnt] = pii(y, w);
  81.     nxt[ecnt] = head[x];
  82.     head[x] = ecnt;
  83.  
  84.     return;
  85. }
  86.  
  87. ll ans[MX][MASK(10)];
  88.  
  89. struct node {
  90.     int u, mask;
  91.     ll dis;
  92.     node(int u = 0, int mask = 0, ll dis = 0): u(u), mask(mask), dis(dis) {}
  93.  
  94.     bool operator <(const node &other) const {
  95.         return dis > other.dis;
  96.     }
  97. };
  98.  
  99. void Dij() {
  100.     priority_queue <node> pq;
  101.     memset(ans, 63, sizeof ans);
  102.  
  103.     for(int i = 1; i <= k; i++) {
  104.         ans[i][MASK(i - 1)] = 0;
  105.         pq.emplace(i, MASK(i - 1), 0);
  106.     }
  107.  
  108.     while(SZ(pq)) {
  109.         node u = pq.top();
  110.         pq.pop();
  111.  
  112.         if(u.dis != ans[u.u][u.mask]) continue;
  113.  
  114.         for(int i = head[u.u]; i > 0; i = nxt[i]) {
  115.             int v, w;
  116.             tie(v, w) = to[i];
  117.  
  118.             ll cost = w + u.dis;
  119.             if(ans[v][u.mask] > cost) {
  120.                 ans[v][u.mask] = cost;
  121.                 pq.emplace(v, u.mask, cost);
  122.             }
  123.  
  124.             int T = FLIP(k, u.mask);
  125.             for(int mask = 1; mask < T; mask++) {
  126.                 int nm = mask | u.mask;
  127.                 if(ans[v][nm] > w + u.dis + ans[v][mask]) {
  128.                     ans[v][nm] = w + u.dis + ans[v][mask];
  129.                     pq.emplace(v, nm, ans[v][nm]);
  130.                 }
  131.             }
  132.         }
  133.     }
  134.  
  135.     return;
  136. }
  137.  
  138. void solveK() {
  139.     for(int i = 1; i <= m; i++) {
  140.         add_edge(e[i].u, e[i].v, e[i].w);
  141.         add_edge(e[i].v, e[i].u, e[i].w);
  142.     }
  143.  
  144.     Dij();
  145.     for(int i = k; i <= n; i++) cout << ans[i][FBIT(k)] << '\n';
  146.  
  147.     return;
  148. }
  149.  
  150. void solve() {
  151.     cin >> n >> m >> k;
  152.     for(int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v >> e[i].w;
  153.  
  154.     if(k <= 10) return solveK(), void();
  155.  
  156.     sort(e + 1, e + m + 1);
  157.     dsu = DSU(n);
  158.  
  159.     memset(dis, 63, sizeof dis);
  160.  
  161.     int F = n - k + 1;
  162.     for(int mask = 1; mask < MASK(F); mask++) {
  163.         ll cur = 0, mst = 0;
  164.         for(int i = 1; i <= m; i++) if(ok(e[i].u, mask) && ok(e[i].v, mask)) {
  165.             if(dsu.join(e[i].u, e[i].v)) {
  166.                 cur += e[i].w;
  167.                 mst++;
  168.             }
  169.         }
  170.  
  171.         if(mst == bit_count(mask) + k - 2) dis[mask] = cur;
  172.         fill(all(dsu.lab), -1);
  173.     }
  174.  
  175.     for(int i = k; i <= n; i++) {
  176.         ll res = 1e18;
  177.         int tmp = MASK(i - k);
  178.         for(int mask = tmp; mask < MASK(F); mask = (mask + 1) | tmp) {
  179.             res = min(res, dis[mask]);
  180.         }
  181.  
  182.         cout << res << '\n';
  183.     }
  184.  
  185.     return;
  186. }
  187.  
  188. int32_t main() {
  189.     ios::sync_with_stdio(false);
  190.     cin.tie(0), cout.tie(0);
  191.     #define task "tet"
  192.     if(fopen(task".inp", "r")) {
  193.         freopen(task".inp", "r", stdin);
  194.         freopen(task".out", "w", stdout);
  195.     }
  196.  
  197.     int testcase = multi == 2 ? 1e9 : 1; if(multi == 1) cin >> testcase;
  198.     while(testcase--) solve();
  199.     return 0;
  200. }
  201.  
Success #stdin #stdout 0.01s 11740KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
4557430888798830399
https://ideone.com/T434u1
language:
C++14 (gcc 8.3)
created:
5 hours 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!