matistjati

Untitled

Jul 9th, 2026
6
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.98 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<int, int> pii;
  9. typedef vector<int> vi;
  10.  
  11. const ll INF = 1e18;
  12.  
  13. template <typename T> pair<T, vector<int>>
  14. weighted_matching(vector<vector<T>> &C) {
  15. int i = sz(C), m = sz(C[0]), c, j, s, r;
  16. vector<T> dist(m), potential(m);
  17. vi row_match(i), col_match(m, -1), cols(m), prev(m);
  18. T d, nd, cost = 0;
  19. for (; i--;) {
  20. rep(c, 0, m) dist[c] = C[i][c], cols[c] = c, prev[c] = i;
  21. for (s = 0;;) {
  22. for (j = s; j < m; j++) if (c = cols[j],
  23. nd = dist[c] - potential[c], j == s || d > nd)
  24. d = nd, swap(cols[s], cols[j]);
  25. if (!~(r = col_match[c = cols[s++]])) break;
  26. rep(j, 0, m) if (dist[j] > (nd = C[r][j] - C[r][c] +
  27. dist[c])) dist[j] = nd, prev[j] = r;
  28. }
  29. for (cost += dist[c]; s--;) j = cols[s],
  30. potential[j] = dist[j] - d;
  31. for (; r != i; swap(c, row_match[r]))
  32. r = col_match[c] = prev[c];
  33. }
  34. return {cost, row_match};
  35. }
  36.  
  37. int main() {
  38. cin.tie(0)->sync_with_stdio(0);
  39. cin.exceptions(cin.failbit);
  40.  
  41. int n, m;
  42. cin >> n >> m;
  43. vector<pii> bottles(n);
  44. rep(i, 0, n) cin >> bottles[i].first >> bottles[i].second;
  45. vector<pii> couriers(m);
  46. rep(i, 0, m) cin >> couriers[i].first >> couriers[i].second;
  47. pii goal;
  48. cin >> goal.first >> goal.second;
  49.  
  50. ll ans = 0;
  51. rep(i, 0, n) {
  52. ans += abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
  53. }
  54. vector<vi> cost(n, vi(n - 1 + m));
  55. rep(i, 0, n) {
  56. rep(j, 0, m) {
  57. cost[i][j] = abs(couriers[j].first - bottles[i].first) + abs(couriers[j].second - bottles[i].second);
  58. }
  59. rep(j, 0, n - 1) cost[i][j + m] = abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
  60. }
  61.  
  62. ans += weighted_matching(cost).first;
  63.  
  64. cout << ans;
  65. }
  66.  
Advertisement
Add Comment
Please, Sign In to add comment