天池 在线编程 旅行计划（暴力回溯）

n<=10 
arr[i][j]<=10000

例1:
输入:[[0,1,2],[1,0,2],[2,1,0]]
输出:4
解释:
[[0,1,2],
 [1,0,2],
 [2,1,0]]
有两种可能的方案。
第一种，城市0->城市1->城市2->城市0，cost=5。
第二种，城市0->城市2->城市1->城市0，cost=4。
返回4

例2:
输入:[[0,10000,2],[5,0,10000],[10000,4,0]]
输出:11

class Solution {
    int ans = INT_MAX;
public:
    /**
     * @param arr: the distance between any two cities
     * @return: the minimum distance Alice needs to walk to complete the travel plan
     */
    int travelPlan(vector<vector<int>> &arr) {
        // Write your code here.
        int n = arr.size();
        if(n == 0) return 0;
        vector<bool> vis(n, false);
        vis[0] = true;
        dfs(arr, vis, 0, 0, 0);
        return ans;
    }
    void dfs(vector<vector<int>> &arr, vector<bool> &vis, int start, int ct, int dis)
    {
        if(ct == arr.size()-1)//走过的城市够个数了
        {
            if(dis + arr[start][0] < ans)
                ans = arr[start][0] + dis;
            return;
        }
        for(int i = 1; i < arr.size(); i++)
        {	// 1 - n-1 城市
            if(vis[i])//走过了，跳过
                continue;
            vis[i] = true;
            dfs(arr, vis, i, ct+1, dis+arr[start][i]);
            vis[i] = false;
        }
    }
};