Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- #define rep(i, a, b) for(int i = a; i < (b); ++i)
- #define all(x) begin(x), end(x)
- #define sz(x) (int)(x).size()
- typedef long long ll;
- typedef pair<ll, ll> pll;
- typedef vector<ll> vl;
- const ll INF = 1e18;
- pair<ll, vl> hungarian(const vector<vl> &a) {
- if (a.empty()) return {0, {}};
- int n = sz(a) + 1, m = sz(a[0]) + 1;
- vl u(n), v(m), p(m), ans(n - 1);
- rep(i,1,n) {
- p[0] = i;
- int j0 = 0; // add "dummy" worker 0
- vl dist(m, INF);
- vl pre(m, -1);
- vector<bool> done(m + 1);
- do { // dijkstra
- done[j0] = true;
- ll i0 = p[j0], j1 = -1, delta = INF;
- rep(j,1,m) if (!done[j]) {
- auto cur = a[i0 - 1][j - 1] - u[i0] - v[j];
- if (cur < dist[j]) dist[j] = cur, pre[j] = j0;
- if (dist[j] < delta) delta = dist[j], j1 = j;
- }
- rep(j,0,m) {
- if (done[j]) u[p[j]] += delta, v[j] -= delta;
- else dist[j] -= delta;
- }
- j0 = j1;
- } while (p[j0]);
- while (j0) { // update alternating path
- ll j1 = pre[j0];
- p[j0] = p[j1], j0 = j1;
- }
- }
- rep(j,1,m) if (p[j]) ans[p[j] - 1] = j - 1;
- return {-v[0], ans}; // min cost
- }
- int main() {
- cin.tie(0)->sync_with_stdio(0);
- cin.exceptions(cin.failbit);
- int n, m;
- cin >> n >> m;
- vector<pll> bottles(n);
- rep(i, 0, n) cin >> bottles[i].first >> bottles[i].second;
- vector<pll> couriers(m);
- rep(i, 0, m) cin >> couriers[i].first >> couriers[i].second;
- pll goal;
- cin >> goal.first >> goal.second;
- ll ans = 0;
- rep(i, 0, n) {
- ans += abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
- }
- vector<vl> cost(n, vl(n - 1 + m));
- rep(i, 0, n) {
- rep(j, 0, m) {
- cost[i][j] = abs(couriers[j].first - bottles[i].first) + abs(couriers[j].second - bottles[i].second);
- }
- rep(j, 0, n - 1) cost[i][j + m] = abs(goal.first - bottles[i].first) + abs(goal.second - bottles[i].second);
- }
- ans += hungarian(cost).first;
- cout << ans;
- }
Advertisement
Add Comment
Please, Sign In to add comment