题目链接：点我
问题：
给你n个点的坐标(x,y,z)。从点(a,b,c) 到另一个点 (p,q,r) 的距离是：|p−a|+|q−b|+max(0,r−c)
问你从一个点为起点，找一条能经过其他所有点的路径，最后回到起点（除了起点可以经过两次，其他所有点只能经过一次
问你这个环的长度最小是多少
问题求解：
假设从顶点s出发，令d(i, V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次，最后回到出发点s的最短路径长度。
我们使用dist(i,j)表示从i点到j点的距离
1、当V是空集的时候，d(i,V)就表示直接从i点回到了s点，也就是dist(i,s)
2、当V不是空集的时候，那么就是对子问题的最优求解。你必须在V这个城市集合中，尝试每一个，并求出最优解。
d(i,V)=min(d(k,V-{k})+dist(i,k)) （V-{k}表示在V集合中把k点去掉
这也就是dp方程了
复杂度：
2n*n2
代码：
#include <cstdio> #include <algorithm> #include <iostream> #include <vector> #include <map> #include <queue> #include <set> #include <ctime> #include <cstring> #include <cstdlib> #include <cmath> #define min(a,b) ((a>b)?b:a) using namespace std; typedef long long ll; const int maxn = 25 + 10; const long long ll_INF=0x3f3f3f3f3f3f3f3fLL; const long long INF=0x3f3f3f3f; int n,w[maxn][maxn],dp[maxn][1<<20],m; vector<int>path; //dp[i][j]保存顶点i到状态j最后回到起始点的最小距离 struct Point { int x,y,z; } point[maxn]; int dist(int i,int j) { return abs(point[i].x-point[j].x)+abs(point[i].y-point[j].y)+max(0,point[j].z-point[i].z); } void TSP() { //我们把起点看作0号节点 for(int i=0; i<n; ++i) { //初始化dp数组 dp[i][0]=w[i][0]; } //按照dp方程求解 for(int j=1; j<m; ++j) //状态 { for(int i=0; i<n; ++i) { dp[i][j]=INF; if( ((j >> (i-1)) & 1) == 1) //这样判断而不是j>>i这样判断，是因为可以直接得到答案就在dp[n][m-1] { //要不然对于dp[n][m-1]的状态肯定每一位都是1，如果换成上面那个判断，那么这个状态的值就是 continue; //INF（因为continue掉了 } for(int k=1; k<n; ++k) { if( ((j >> (k-1)) & 1) == 0) { continue; } if( dp[i][j] > w[i][k] + dp[k][j^(1<<(k-1))]) { dp[i][j] = w[i][k] + dp[k][j^(1<<(k-1))]; } } } } } //判断结点是否都以访问,不包括0号结点 bool isVisited(bool visited[]) { for(int i = 1 ; i<n ; i++) { if(visited[i] == false) { return false; } } return true; } //获取最优路径，保存在path中,根据动态规划公式反向找出最短路径结点 void getPath() { //标记访问数组 bool visited[n] = {false}; //前驱节点编号 int pioneer = 0,minn = INF, S = m - 1,temp ; //把起点结点编号加入容器 path.push_back(0); while(!isVisited(visited)) { for(int i=1; i<n; i++) { if(visited[i] == false && (S&(1<<(i-1))) != 0) { if(minn > w[i][pioneer] + dp[i][(S^(1<<(i-1)))]) { minn = w[i][pioneer] + dp[i][(S^(1<<(i-1)))] ; temp = i; } } } pioneer = temp; path.push_back(pioneer); visited[pioneer] = true; S = S ^ (1<<(pioneer - 1)); minn = INF; } } //输出路径 void printPath() { cout<<"最小路径为："; vector<int>::iterator it = path.begin(); for(it ; it != path.end(); it++) { cout<<*it<<"--->"; } //单独输出起点编号 cout<<0; } int main() { //printf("%d ",(3>>(-1))); 6 scanf("%d",&n); m=(1<<(n-1)); for(int i=0; i<n; ++i) { scanf("%d%d%d",&point[i].x,&point[i].y,&point[i].z); } for(int i=0; i<n; ++i) { for(int j=0; j<n; ++j) { if(i==j) w[i][j]=0; else w[i][j]=dist(i,j); } } TSP(); printf("%d ",dp[0][m-1]); //下面用于输出路径 // getPath(); // printPath(); return 0; }