题解 | 收集纸片

暴力枚举每种方案，复杂度

#include <algorithm>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

int n;
vector<pair<int, int>> pos;

int Dis(const pair<int, int>& a, const pair<int, int>& b) {
    return abs(a.first - b.first) + abs(a.second - b.second);
}

void Solve() {
    pair<int, int> st;
    cin >> n >> n >> st.first >> st.second >> n;
    pos.resize(n);
    for (auto& [x, y] : pos) {
        cin >> x >> y;
    }
    sort(pos.begin(), pos.end());
    int mini = INT_MAX;
    do {
        int cur = Dis(pos.front(), st) + Dis(st, pos.back());
        for (int i = 1; i < n; i++) {
            cur += Dis(pos[i], pos[i - 1]);
        }
        mini = min(mini, cur);
    } while (next_permutation(pos.begin(), pos.end()));
    cout << "The shortest path has length " << mini << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        Solve();
    }
    return 0;
}