双调TSP问题最牛逼的解法，不接受所有人反驳

为什么我取这个标题呢？因为我的解 又简单 又好写

我找遍了许多答案，却没发现一个满意的，通过询问GPT，再通过自己的改善，总算得到正确的解了！！！

首先你得明白是如何递推的。

我们规定dp[i][j] 是分别以i,j为结尾的 TSP路线

然后要保证结点i和j为不同的边，简单认为为上下两条边就行了.

先给[0][1]初始化，我们需要知道如何递推

核心代码如下：

 for (int j = 2; j < n; ++j){for (int i = 0; i < j - 1; ++i){dp[i][j] = dp[i][j - 1] + euclidean_distance(points[j - 1], points[j]);// prt(dp, cnt);}double min_value = 1e9;for (int k = 0; k < j - 1; ++k){min_value = min(min_value, dp[k][j - 1] + euclidean_distance(points[k], points[j]));}dp[j - 1][j] = min_value;// prt(dp, cnt);}

然后你会发现 你一脸懵逼了。 这是在更新什么？ 容我来解释一下

对j进行枚举，j是每次新加的点，从结点2开始。我们需要更新它相对于j-1 之外点的dp[i][j]。

你会疑惑，为什么j和j-1连体了？也就是说，我每次链接的是j-1和j这条边。因为我们需要让i和j保持为不同方向，让j-1和j保持同向，所以链接j-1和j。

然后再对j-1和j 找出最小的dp[j-1][j] 更新出所有边

但是这里要注意，这里的j-1和j 是不同的边，也就是说j-1和j 一个在上 一个在下。 为什么我们要这么写？ 因为我们最后的答案，肯定是两个相邻的两个节点求最小值。因此这么更新。

然后在i-1里面的节点，取一个点，用来更新dp[k][j-1] 和dist(p[k],p[j])，让k和j同边了

最后找答案的过程 也比较好理解

 for (int i = 0; i < n - 1; ++i){result = min(result, dp[i][n - 1] + euclidean_distance(points[i], points[n - 1]));}

针对最后一个结点 进行枚举。从0结点开始枚举，链接该结点和最后结点的距离，然后再求dp[i][n-1] 得到答案

最终代码

#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
// 定义二维点
struct Point
{double x, y;
};// 计算两点之间的欧氏距离
double dist(Point a, Point b)
{return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}void prt(vector<vector<double>> dp, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (abs(dp[i][j] - 1e9) < 1e-7)cout << "0 ";elsecout << fixed << setprecision(2) << dp[i][j] << " ";}cout << endl;}
}
int main()
{int n;int cnt;cin >> n;cnt = n;vector<vector<double>> dp(n, vector<double>(n, 1e9)); // 初始化为一个很大的值// 输入点坐标vector<Point> p(n);for (int i = 0; i < n; ++i){cin >> p[i].x >> p[i].y;}// 按照 x 坐标从小到大排序sort(p.begin(), p.end(), [](Point a, Point b){ return a.x < b.x; });// 动态规划表// 初始状态：第一个点到第二个点的路径dp[0][1] = dist(p[0], p[1]);// 动态规划求解最短路径for (int j = 2; j < n; ++j){for (int i = 0; i < j - 1; ++i){dp[i][j] = dp[i][j - 1] + dist(p[j - 1], p[j]);// prt(dp, cnt);}double min_value = 1e9;for (int k = 0; k < j - 1; ++k){min_value = min(min_value, dp[k][j - 1] + dist(p[k], p[j]));}dp[j - 1][j] = min_value;// prt(dp, cnt);}// 最后求解从最右点回到最左点的最短路径double result = 1e9;for (int i = 0; i < n - 1; ++i){result = min(result, dp[i][n - 1] + dist(p[i], p[n - 1]));}// 输出结果，保留两位小数cout << fixed << setprecision(2) << result << endl;return 0;
}