题解 | #毕业旅行问题#

经典TF问题

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    while(cin>>n){
        vector<vector<int>> dist(n,vector<int>(n,0));//图建立
        int x;
        for(int i =0; i< n;i++){
            for(int j =0; j< n;j++){
                cin>>x;
                dist[i][j] = x;
            }
        }
        //dp旅行商问题
        vector<vector<int>> dp(n,vector<int>(1<<(n-1),0));// n-1是为了只需要除了第一个点的其他点的位
        dp[0][0] = 0;
        int v = 1<<(n-1);
        for(int j = 0; j< v ;j++){
            for(int i =0; i< n;i++){
                if(j==0){
                    dp[i][j]= dist[i][j];//表示从第i个城市到第j(0)个城市的最小路径。正好就是第i个城市去第0个城市的距离。
                }else{
                    dp[i][j] = INT_MAX;
                    for(int k = 1; k < n; k++){
                        //表示第k位城市。
                        int index = 1<<(k-1);
                        //开始动归主要的表达式，首先我们要剪枝确保这个城市是可供访问的备选点
                        if((index&j)>0){

                            //表示j城市集内除了第k位其他的别的城市
                            int other = j ^ index;
                            dp[i][j] = min(dist[i][k] + dp[k][other] ,dp[i][j]);

                        }

                    }

                }
            }

        }


        cout<<dp[0][v-1]<<endl;//最后返回 dp[0][{1,2,3}] = dp[0][v-1]



    }


}