一个简单的货郎担问题，用状态压缩dp可以解决；
解法：
d(i,S)=min{d(j,S-{j})+dis(i,j) | j belongs to S};
边界条件：d(i,{})=dis(0,i).
最终答案：d(0,{1,2,3```n-1})
时间复杂度：O(n^2*2^b);
代码：
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 using namespace std; 6 int dp[1024][11],dis[11][11],posx[11],posy[11]; 7 8 int main() 9 { 10 int t,x,y,n; 11 scanf("%d",&t); 12 while(t--) 13 { 14 memset(dis,0,sizeof dis); 15 scanf("%d%d",&x,&y); 16 scanf("%d%d",&posx[0],&posy[0]); 17 scanf("%d",&n); 18 for(int i=1; i<=n; i++) 19 scanf("%d%d",&posx[i],&posy[i]); 20 for(int i=0; i<=n; i++) 21 for(int j=0; j<i; j++) 22 dis[i][j]=dis[j][i]=abs(posx[i]-posx[j])+abs(posy[i]-posy[j]); 23 memset(dp,0x1f,sizeof dp); 24 for (int i=0; i<(2<<n); ++i) 25 for (int j=0; j<=n; ++j) 26 { 27 dp[1<<j][j]=dis[0][j]; 28 if(i&(1<<j)) 29 for (int k=0; k<=n; ++k) 30 { 31 if((i-(1<<j))&(1<<k)) 32 dp[i][j]=min(dp[i-(1<<j)][k]+dis[k][j],dp[i][j]); 33 } 34 } 35 int ans=dp[(2<<n)-1][0]; 36 for(int i=1; i<=n; i++) 37 ans=min(dp[(2<<n)-1][i]+dis[i][0],ans); 38 printf("The shortest path has length %d ",ans); 39 } 40 return 0; 41 }