Submission #73386050

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ff first
#define ss second
using namespace std;
using namespace __gnu_pbds;
const int INF = 1e9;
const ll MOD = 1e9 + 7;

struct seg {
    int n;
    vector<int> t;
    seg(int n): n(n), t(4*n, 1) {}
    void upd(int id, int v, int x, int lx, int rx){
        if (lx == rx) {
            t[x] = v;
            return;
        }
        int m = (lx + rx) / 2;
        if (id <= m) upd(id, v, x*2, lx, m);
        else upd(id, v, x*2+1, m+1, rx);
        t[x] = t[x*2] * t[x*2+1];
    }
    void upd(int id, int v) {
        upd(id, v, 1, 1, n);
    }
    int qry(int l, int r, int x, int lx, int rx){
        if (r < lx || rx < l) return 1;
        if (l <= lx && rx <= r) return t[x];
        int m = (lx + rx) / 2;
        return qry(l, r, x*2, lx, m) *
               qry(l, r, x*2+1, m+1, rx);
    }
    int qry(int l, int r) {
        return qry(l, r, 1, 1, n);
    }
};

ll n, m;

pll get_pos(ll x) {
    x--;
    return {x / n, x % n};
}

ll dist(pll a, pll b) {
    return llabs(a.ff - b.ff) + llabs(a.ss - b.ss);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    ll s, t;
    cin >> s >> t;
    auto ps = get_pos(s);
    auto pt = get_pos(t);
    if(m == 0){
        cout << dist(ps, pt);
        return 0;
    }
    vector<ll> p(m);
    for (int i = 0; i < m; i++) cin >> p[i];
    vector<pll> pos(m);
    for (int i = 0; i < m; i++) {
        pos[i] = get_pos(p[i]);
    }
    int fl = (1 << m);
    const ll INF = 4e18;
    vector<vector<ll>> dp(fl, vector<ll>(m, INF));
    for (int i = 0; i < m; i++) {
        dp[1 << i][i] = dist(ps, pos[i]);
    }
    for (int mk = 0; mk < fl; mk++) {
        for (int i = 0; i < m; i++) {
            if (!(mk & (1 << i))) continue;
            if (dp[mk][i] == INF) continue;
            for (int j = 0; j < m; j++) {
                if(mk & (1 << j)) continue;
                int nmk = mk | (1 << j);
                dp[nmk][j] = min(dp[nmk][j], dp[mk][i] + dist(pos[i], pos[j]));
            }
        }
    }
    ll ans = INF;
    int all = fl - 1;
    for (int i = 0; i < m; i++) {
        ans = min(ans, dp[all][i] + dist(pos[i], pt));
    }
    cout << ans;
}

Submission Info

Judge Result