matistjati

Untitled

Jul 9th, 2026
6
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define rep(i, a, b) for(int i = a; i < (b); ++i)
  5. #define all(x) begin(x), end(x)
  6. #define sz(x) (int)(x).size()
  7. typedef long long ll;
  8. typedef pair<ll, ll> pll;
  9. typedef vector<ll> vl;
  10.  
  11. const ll INF = 1e18;
  12.  
  13. pair<ll, vl> hungarian(const vector<vl> &a) {
  14. if (a.empty()) return {0, {}};
  15. int n = sz(a) + 1, m = sz(a[0]) + 1;
  16. vl u(n), v(m), p(m), ans(n - 1);
  17. rep(i,1,n) {
  18. p[0] = i;
  19. int j0 = 0; // add "dummy" worker 0
  20. vl dist(m, INF);
  21. vl pre(m, -1);
  22. vector<bool> done(m + 1);
  23. do { // dijkstra
  24. done[j0] = true;
  25. ll i0 = p[j0], j1 = -1, delta = INF;
  26. rep(j,1,m) if (!done[j]) {
  27. auto cur = a[i0 - 1][j - 1] - u[i0] - v[j];
  28. if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
  29. if (dist[j] < delta) delta = dist[j], j1 = j;
  30. }
  31. rep(j,0,m) {
  32. if (done[j]) u[p[j]] += delta, v[j] -= delta;
  33. else dist[j] -= delta;
  34. }
  35. j0 = j1;
  36. } while (p[j0]);
  37. while (j0) { // update alternating path
  38. ll j1 = pre[j0];
  39. p[j0] = p[j1], j0 = j1;
  40. }
  41. }
  42. rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
  43. return {-v[0], ans}; // min cost
  44. }
  45.  
  46. int main() {
  47. cin.tie(0)->sync_with_stdio(0);
  48. cin.exceptions(cin.failbit);
  49.  
  50. int n, m;
  51. cin >> n >> m;
  52. vector<pll> bottles(n);
  53. rep(i, 0, n) cin >> bottles[i].first >> bottles[i].second;
  54. vector<pll> couriers(m);
  55. rep(i, 0, m) cin >> couriers[i].first >> couriers[i].second;
  56. pll goal;
  57. cin >> goal.first >> goal.second;
  58.  
  59. ll ans = 0;
  60. rep(i, 0, n) {
  61. ans += abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
  62. }
  63. vector<vl> cost(n, vl(n - 1 + m));
  64. rep(i, 0, n) {
  65. rep(j, 0, m) {
  66. cost[i][j] = abs(couriers[j].first - bottles[i].first) + abs(couriers[j].second - bottles[i].second);
  67. }
  68. rep(j, 0, n - 1) cost[i][j + m] = abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
  69. }
  70.  
  71. ans += hungarian(cost).first;
  72.  
  73. cout << ans;
  74. }
  75.  
Advertisement
Add Comment
Please, Sign In to add comment