毕业旅行问题

题目描述：

小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。

输入描述:

城市个数n（1<n≤20，包括北京）

城市间的车票价钱 n行n列的矩阵 m[n][n]

输出描述:

最小车费花销 s

示例1

输入

4
0 2 6 5
2 0 4 4
6 4 0 2
5 4 2 0

输出

13

说明

共 4 个城市，城市 1 和城市 1 的车费为0，城市 1 和城市 2 之间的车费为 2，城市 1 和城市 3 之间的车费为 6，城市 1 和城市 4 之间的车费为 5，依次类推。假设任意两个城市之间均有单程票可购买，且票价在1000元以内，无需考虑极端情况。

思路:

用状态压缩动态规划来写，1代表已经走过这个地方了，解释一下代码

第一层循环代表所有情况，第二层代表下一个要去的城市是第几个城市，第三层循环代表中间结点城市。

i>>j &1 //判断i的第j位是不是1

i^(1<<j) //把i的第j位置为1

#### 代码:

```golang
#include<stdio.h>
#include<string.h>
int min(int a,int b){
    if(a > b){
        return b;
    }else{
        return a;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    int dp[1<<n][n];
    
    int num[n][n];
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%d",&num[i][j]);
    memset(dp,0x3f,sizeof(dp));
    dp[1][0] = 0;
    for(int i=1;i<(1<<n);i+=2){
        for(int j=0;j<n;j++){
            if((i>>j &1==0)) continue;
            for(int k=0;k<n;k++){
                if(j==k) continue;
                if((i>>k)&1==0) continue;
                dp[i][j] = min(dp[i][j],dp[i^(1<<j)][k]+num[k][j]);
            }
        }
    }
    int res =9999;
    for(int i=0;i<n;i++){
        res = min(res,dp[(1<<n)-1][i]+num[i][0]);
    }
    printf("%d\n",res);
}

代码效率：

运行时间：78ms, 超过33.33%用C提交的代码
占用内存：18732KB, 超过15.69%用C提交的代码