题解 | 收集纸片

数据量很小，直接全排列枚举前往点的顺序,再按照path顺序遍历所有点求出答案，时间复杂度为O(n!*n);

#include <bits/stdc++.h>
using namespace std;
int n;
int sx,sy;
int a[11],b[11];
vector<int>path;
bool vis[11];
int ans;
void upd()
{
    int curans = 0;
    int cx =sx,cy=sy;
    for(auto i:path)
    {   
        curans += abs(cx-a[i])+abs(cy-b[i]);
        cx =a[i];
        cy = b[i];
    }
    curans += abs(cx-sx)+abs(cy-sy);
    ans = min(ans,curans);
}

void dfs()
{
    if(path.size()==n)
    {
        upd();
        return ;
    }
    for(int i=1;i<=n;i++)
    {
        if(vis[i])continue;
        path.push_back(i);
        vis[i]=true;
        dfs();
        path.pop_back();
        vis[i]=false;
    }

}

void solve()
{
    ans = INT_MAX;

    int sz1,sz2;
    cin>>sz1>>sz2;
    cin>>sx>>sy;
    cin>>n;

    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
    }

    dfs();
    cout<<"The shortest path has length ";
    cout<<ans<<endl;

}

int main()
{
    int _;
    cin>>_;
    while(_--)
    {
        solve();
    }
    

    return 0;
}