Submission #73389188

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vll = vector<ll>;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define f first
#define s second

#define rep(i, a, b) for (int i = (a); i < (b); ++i)
#define per(i, a, b) for (int i = (b) - 1; i >= (a); --i)

void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

#ifdef LOCAL
#define debug(x) cerr << #x << " = " << (x) << endl;
#else
#define debug(x)
#endif

const int INF = 1e9 + 7;
const ll LINF = 1e18;

ll dp[(1<<20)+10][20];
ll record[(1<<20)+10][20];
vector<pll> use;
ll n,m;

ll dis(int a,int b){
    return llabs(use[a].first-use[b].first)+llabs(use[a].second-use[b].second);
}

void solve() {
    cin>>n>>m;
    ll S,t;
    cin>>S>>t;
    use.pb({S/n+1-((S%n)==0),S%n+n*((S%n)==0)});
    use.pb({t/n+1-((t%n)==0),t%n+n*((t%n)==0)});
    rep(i,0,m){
        ll tmp;
        cin>>tmp;
        use.pb({tmp/n+1-((tmp%n)==0),tmp%n+n*((tmp%n)==0)});
    }
    // for(auto u:use){
    //     cerr<<u.first<<" "<<u.second<<"\n";
    // }
    m++;
    m++;
    rep(i,0,(1<<m)){
        rep(j,0,m){
            dp[i][j]=1e18;
            record[i][j]=-1;
        }
    }
    dp[1][0]=0;
    // rep(i,0,m){
        // dp[(1<<i)][i]=0;
    // }
    // dp[0][0]=0;
    // dp[1][1]=0;
    rep(i,0,(1<<m)){
        rep(j,0,m){
            if((i&(1<<j))==0)continue;
            rep(k,0,m){
                if((i&(1<<k))==0)continue;
                if(j==k)continue;
                if(dp[(i^(1<<j))][k]+dis(j,k)<dp[i][j]){
                    dp[i][j]=dp[(i^(1<<j))][k]+dis(j,k);
                    record[i][j]=k;
                }
                // dp[i][j]=min(dp[i][j],dp[(i^(1<<j))][k]+dis(j,k));
                // dp[i][j]=min(dp[i][j],dp[i][k]+dis(j,k));
            }
        }
        // rep(j,0,m){
        //     if(!(i&(1<<j)))continue;
        //     rep(k,0,m){
        //         if(!(i&(1<<k)))continue;
        //         if(j==k)continue;
        //         dp[i][j]=min(dp[i][j],dp[i][k]+dis(j,k));
        //         // dp[i][j]=min(dp[i][j],dp[i][k]+dis(j,k));
        //     }
        // }
    }
    // rep(i,0,(1<<m)){
    //     rep(j,0,m){
    //         if(dp[i][j]==1e18)cerr<<-1<<" ";
    //         else cerr<<dp[i][j]<<' ';
    //     }
    //     cerr<<"\n";
    // }
    vll sstt;
    // sstt.pb(1);
    int star=1;
    int sta=(1<<m)-1;
    while(sta>0){
        // cerr<<sta<<" "<<star<<"\n";
        sstt.pb(star);
        ll tmp=sta;
        sta^=(1<<star);
        star=record[tmp][star];
    }
    // cerr<<"\n";
    // for(auto u:sstt){
    //     cerr<<u<<" ";
    // }
    // cerr<<m;
    cout<<dp[(1<<m)-1][1];
}

int main() {
    fast_io();
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Submission Info

Judge Result