fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. PROBLEM (simple)
  6. ----------------
  7. There are n locations. Each location initially has resources.
  8.  
  9. Moving ALL resources from i -> j costs cost[i][j].
  10. You are allowed to move via intermediate locations (i -> x -> j) if that is cheaper.
  11.  
  12. Goal:
  13. After all moves, resources should remain in AT MOST k locations (you choose which k hubs).
  14. Every other location must send its resources to one of the chosen hubs.
  15. Minimize total cost.
  16.  
  17. Key observation
  18. ---------------
  19. 1) Since routing via intermediates is allowed, first compute the cheapest cost between every pair:
  20.    -> Floyd–Warshall gives dist[i][j] = minimum shipping cost from i to j.
  21.  
  22. 2) If we choose a set of hubs S (|S| <= k), then each location i will ship to the cheapest hub:
  23.       cost for i = min_{h in S} dist[i][h]
  24.    Total cost for hub set S:
  25.       sum_i min_{h in S} dist[i][h]
  26.  
  27. 3) For small n (<= ~20–22), we can try all hub sets using a bitmask:
  28.    mask bit h = 1  => hub h is kept
  29.    For each mask, compute total cost efficiently in O(n * 2^n):
  30.  
  31.    For each location i:
  32.       bestToSet[mask] = min_{h in mask} dist[i][h]
  33.    Then:
  34.       totalCost[mask] = sum over i of bestToSet[mask]
  35.  
  36.    Answer = min totalCost[mask] for popcount(mask) <= k
  37.  
  38. Complexity
  39. ----------
  40. Floyd–Warshall: O(n^3)
  41. Bitmask DP:     O(n * 2^n)
  42. Memory:         O(n^2) + O(2^n)
  43.  
  44. NOTE:
  45. - This exact approach is practical only for n <= 20–22.
  46. - If your input uses -1 for "no direct path", convert -1 to INF while reading.
  47. */
  48.  
  49. int main() {
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(nullptr);
  52.  
  53.     int n, k;
  54.     cin >> n >> k;
  55.  
  56.     const long long INF = (1LL << 62);
  57.  
  58.     // Exact bitmask DP becomes infeasible beyond ~22
  59.     if (n > 22) {
  60.         cout << -1 << "\n";
  61.         return 0;
  62.     }
  63.     if (k == 0) {                 // usually not present in OAs, but safe
  64.         cout << -1 << "\n";
  65.         return 0;
  66.     }
  67.  
  68.     // Read cost matrix
  69.     vector<vector<long long>> dist(n, vector<long long>(n));
  70.     for (int i = 0; i < n; i++) {
  71.         for (int j = 0; j < n; j++) {
  72.             long long x;
  73.             cin >> x;
  74.  
  75.             // If your problem says "-1 means no path", use:
  76.             // dist[i][j] = (x == -1 ? INF : x);
  77.  
  78.             dist[i][j] = x;
  79.         }
  80.     }
  81.  
  82.     // Keeping location i means no move => 0 cost on diagonal
  83.     for (int i = 0; i < n; i++) dist[i][i] = 0;
  84.  
  85.     // Floyd–Warshall: compute shortest shipping costs (allow intermediates)
  86.     for (int mid = 0; mid < n; mid++) {
  87.         for (int i = 0; i < n; i++) {
  88.             if (dist[i][mid] >= INF / 2) continue; // i->mid unreachable
  89.             for (int j = 0; j < n; j++) {
  90.                 if (dist[mid][j] >= INF / 2) continue; // mid->j unreachable
  91.                 long long cand = dist[i][mid] + dist[mid][j];
  92.                 if (cand < dist[i][j]) dist[i][j] = cand;
  93.             }
  94.         }
  95.     }
  96.  
  97.     // If we can keep all locations, no moves needed
  98.     if (k >= n) {
  99.         cout << 0 << "\n";
  100.         return 0;
  101.     }
  102.  
  103.     int ALL = 1 << n;
  104.  
  105.     // totalCost[mask] = total cost if we keep exactly the hub set represented by mask
  106.     vector<long long> totalCost(ALL, 0);
  107.  
  108.     // bestToSet[mask] (reused per location i):
  109.     // bestToSet[mask] = min_{h in mask} dist[i][h]
  110.     vector<long long> bestToSet(ALL);
  111.  
  112.     // Build totalCost by processing each location one at a time
  113.     for (int i = 0; i < n; i++) {
  114.         bestToSet[0] = INF; // empty hub set is invalid
  115.  
  116.         // DP over masks:
  117.         // bestToSet[mask] = min(bestToSet[mask without lowest bit], dist[i][hub(lowest bit)])
  118.         for (int mask = 1; mask < ALL; mask++) {
  119.             int hub = __builtin_ctz((unsigned)mask); // index of lowest set bit
  120.             int prev = mask & (mask - 1);            // remove that bit
  121.             bestToSet[mask] = min(bestToSet[prev], dist[i][hub]);
  122.         }
  123.  
  124.         // Add this location's contribution into totalCost (skip mask=0)
  125.         for (int mask = 1; mask < ALL; mask++) {
  126.             __int128 sum = (__int128)totalCost[mask] + bestToSet[mask];
  127.             totalCost[mask] = (sum > (__int128)INF) ? INF : (long long)sum;
  128.         }
  129.     }
  130.  
  131.     // Answer = best totalCost[mask] among masks with <= k hubs
  132.     long long ans = INF;
  133.     for (int mask = 1; mask < ALL; mask++) {
  134.         if (__builtin_popcount((unsigned)mask) <= k) {
  135.             ans = min(ans, totalCost[mask]);
  136.         }
  137.     }
  138.  
  139.     // If unreachable paths exist, ans may remain INF
  140.     if (ans >= INF / 2) cout << -1 << "\n";
  141.     else cout << ans << "\n";
  142.  
  143.     return 0;
  144. }
Success #stdin #stdout 0s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-1
https://ideone.com/3vUvs8
language:
C++14 (gcc 8.3)
created:
2 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!