There are n cities, and the adjacency matrixarr represents the distance between any two cities.arr[i][j]represents the distance from city i to city j.Alice made a travel plan on the weekend. She started from city 0, then she traveled other cities 1 ~ n-1, and finally returned to city 0. Alice wants to know the minimum distance she needs to walk to complete the travel plan. Return this minimum distance. Each city can only pass once except city 0.

-------------------------------------------------------------

public class Solution {
    /**
     * @param arr: the distance between any two cities
     * @return: the minimum distance Alice needs to walk to complete the travel plan
     */
    static int res;
    public int travelPlan(int[][] arr) {
        // Write your code here.
        res = Integer.MAX_VALUE;
        int n = arr.length;
        boolean[] visited = new boolean[n];
        DFS(0, 0, 0, n, arr, visited);
        return res;
    }
    
    public static void DFS(int step, int curDis, int curCity, int n, int[][] arr, boolean[] visited) {
        if(step == n) {
            if(curCity == 0) {
                res = res < curDis ? res : curDis;
                return;
            }
        }
        if(curDis >= res)
            return;
        for(int i = 0; i < n; i++) {
            if(curCity == i)
                continue;
            if(!visited[i]) {
                visited[i] = true;
                DFS(step+1, curDis+arr[curCity][i], i, n, arr, visited);
                visited[i] = false;
            }
        }
        
    }
}