题解 | 收集纸片

#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define dbg(x) cout<<#x<<": "<<x<<endl;
#define endl '\n'
#define int long long
const int inf=LLONG_MAX;
void submit(int x){
    cout<<"The shortest path has length "<<x<<endl;
}
int dis(pair<int,int> a,pair<int,int> b){
    return abs(a.first-b.first)+abs(a.second-b.second);
}
vector<pair<int,int> > rec;
int cal(vector<int>&x){
    int n=x.size()-1,sum=0;
    for(int i=0;i<n;i++){
        sum+=dis(rec[x[i]],rec[x[i+1]]);
    }
    sum+=dis(rec[x[n]],rec[0]);
    return sum;
}
void solve(){
    int tmp;cin>>tmp>>tmp;
    int a,b;cin>>a>>b;
    int n;cin>>n;
    rec=vector<pair<int,int> >(n+1);
    rec[0]={a,b};
    for(int i=1;i<=n;i++)cin>>rec[i].first>>rec[i].second;
    vector<int> ord(n+1);
    for(int i=1;i<=n;i++)ord[i]=i;
    int ans=inf;
    do{
        ans=min(ans,cal(ord));
    }while(next_permutation(ord.begin()+1,ord.end()));
    submit(ans);
}
signed main(){
    IOS;
    int t=1;
    cin>>t;
    while(t--)solve();
    return 0;
}

枚举所有遍历点的顺序即可，这里给出一种简单的，进行全排列的方法