题目链接 先跑一个最短路，然后直接状压dp用最短路转移即可。
#pragma GCC optimize(2) #pragma GCC optimize(3) #include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 2e5 + 10; #define fi first #define se second #define pb push_back #define wzh(x) cerr<<#x<<'='<<x<<endl; LL dp[1<<17][17]; int n; int x[N],y[N],z[N]; LL dis[18][18]; int main() { ios::sync_with_stdio(false); cin>>n; for(int i=1;i<=n;i++)cin>>x[i]>>y[i]>>z[i]; for(int i=1;i<=n;i++){ dis[i][i]=0; for(int j=1;j<=n;j++){ dis[i][j]=abs(x[j]-x[i])+abs(y[j]-y[i])+max(0,z[j]-z[i]); } } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ for(int k=1;k<=n;k++){ dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]); } } } memset(dp,0x3f3f3f,sizeof dp); dp[1][0]=0; for(int i=1;i<1<<n;i++){ for(int j=0;j<n;j++){ if(!(i>>j&1)) { for (int k = 0; k < n; k++) { if(i>>k&1){ dp[i|1<<j][j]=min(dp[i|1<<j][j],dp[i][k]+dis[k+1][j+1]); } } } } } LL ans=1e18; for(int i=0;i<n;i++){ ans=min(ans,dp[(1<<n)-1][i]+dis[i+1][1]); } cout<<ans<<'\n'; return 0; }