题目名称（假设：平面路径规划问题）

题目描述

在平面直角坐标系中，给定起点 ( S ) 和终点 ( T )，以及 ( n ) 个转弯点 ( A_1, A_2, \ldots, A_n )。要求从 ( S ) 出发，依次经过所有转弯点，最终到达 ( T )，且转弯点的顺序不保证按距离 ( S ) 由近到远排列。求满足条件的最短路径长度。

解题思路

本题可采用动态规划（DP）结合状态压缩的方法求解。由于转弯点顺序不固定，需考虑所有可能的访问顺序，但全排列复杂度高，因此通过位掩码表示已访问的转弯点集合，利用DP优化状态转移。

关键步骤

1. 距离预处理：计算起点 ( S ) 到各转弯点的距离、各转弯点之间的距离，以及各转弯点到终点 ( T ) 的距离。
2. DP状态定义：设 ( dp[mask][u] ) 表示经过 ( mask ) 中所有转弯点（( mask ) 为位掩码，( u ) 为当前所在转弯点的索引）时的最短路径长度。
3. 初始化：对于每个转弯点 ( i )，( dp[1<<i][i] = \text{distance}(S, A_i) )，即从起点直接到第 ( i ) 个转弯点的距离。
4. 状态转移：对于每个位掩码 ( mask ) 和当前点 ( u )，遍历所有未访问的转弯点 ( v )，更新 ( dp[mask | (1<<v)][v] ) 为 ( dp[mask][u] + \text{distance}(A_u, A_v) ) 的最小值。
5. 计算最终答案：遍历所有转弯点 ( u )，计算 ( dp[\text{full_mask}][u] + \text{distance}(A_u, T) )，取最小值即为最短路径长度（( \text{full_mask} ) 为包含所有转弯点的位掩码）。

代码实现

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

const double INF = 1e18;

// 计算两点间欧几里得距离
double distance(pair<double, double> a, pair<double, double> b) {
    double dx = a.first - b.first;
    double dy = a.second - b.second;
    return sqrt(dx*dx + dy*dy);
}

int main() {
    int n;
    cin >> n; // 转弯点数量
    vector<pair<double, double>> points(n); // 存储转弯点坐标
    for (int i = 0; i < n; ++i) {
        cin >> points[i].first >> points[i].second;
    }
    pair<double, double> S, T;
    cin >> S.first >> S.second >> T.first >> T.second;

    // 预处理距离矩阵
    vector<vector<double>> dist(n, vector<double>(n)); // dist[i][j] = distance(A_i, A_j)
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) { // 允许i=j（但实际不会用到）
            dist[i][j] = distance(points[i], points[j]);
        }
    }
    
    // 起点到各转弯点的距离
    vector<double> start_dist(n);
    for (int i = 0; i < n; ++i) {
        start_dist[i] = distance(S, points[i]);
    }
    
    // 各转弯点到终点的距离
    vector<double> end_dist(n);
    for (int i = 0; i < n; ++i) {
        end_dist[i] = distance(points[i], T);
    }

    int full_mask = (1 << n) - 1; // 表示所有转弯点均已访问的掩码
    vector<vector<double>> dp(1 << n, vector<double>(n, INF)); // dp[mask][u]

    // 初始化：仅访问单个转弯点的情况
    for (int i = 0; i < n; ++i) {
        dp[1 << i][i] = start_dist[i];
    }
    
    // 状态转移：遍历所有掩码和当前点
    for (int mask = 1; mask < (1 << n); ++mask) {
        for (int u = 0; u < n; ++u) {
            if (!(mask & (1 << u))) continue; // u不在当前掩码中，跳过
            for (int v = 0; v < n; ++v) {
                if (mask & (1 << v)) continue; // v已在当前掩码中，跳过
                
                int new_mask = mask | (1 << v); // 新增访问v后的新掩码
                dp[new_mask][v] = min(dp[new_mask][v], dp[mask][u] + dist[u][v]);
            }
        }
    }

    // 计算最终答案：经过所有转弯点后到终点的最短距离
    double ans = INF;
    for (int u = 0; u < n; ++u) {
        ans = min(ans, dp[full_mask][u] + end_dist[u]);
    }
    
    printf("%.2f\n", ans); // 输出结果，保留两位小数
    return 0;
}

复杂度分析

• 时间复杂度：( O(n^2 \cdot 2^n) )，其中 ( n ) 为转弯点数量。状态数为 ( n \cdot 2^n )，每个状态需遍历 ( n ) 个未访问点。
• 空间复杂度：( O(n \cdot 2^n) )，主要为DP数组的空间开销。

注意事项

• 当 ( n \leq 15 ) 时，该方法高效可行；若 ( n ) 较大（如 ( n > 15 )），需考虑近似算法（如贪心）。
• 题目中“转弯点不保证按从起点由近到远排列”的条件通过状态转移的全遍历处理，无需预设顺序。

本题不保证转弯点按从起点由近到远的顺序排列。