/**
 * @param nums: A list of integers.
 * @return: A list of permutations.
 *          we will sort your return value in output
 */
// Permute 生成所有可能的排列组合
func Permute(nums []int) [][]int {
	var results [][]int
	if nums == nil {
		return results
	}

	visited := make([]bool, len(nums))
	dfs(nums, visited, []int{}, &results)
	return results
}

// dfs 递归生成排列组合
// 递归的定义
func dfs(nums []int,
	visited []bool,
	permutation []int,
	results *[][]int) {

	// 递归的出口
	if len(permutation) == len(nums) {
		// 深拷贝当前排列并添加到结果集中
		temp := make([]int, len(permutation))
		copy(temp, permutation)
		*results = append(*results, temp)
		return
	}

	// 递归的拆解
	for i := 0; i < len(nums); i++ {
		if visited[i] {
			continue
		}
		// 添加当前数字到排列中，并标记为已访问
		permutation = append(permutation, nums[i])
		visited[i] = true
		// 递归继续生成排列
		dfs(nums, visited, permutation, results)
		// 回溯，移除最后一个数字，并标记为未访问
		visited[i] = false
		permutation = permutation[:len(permutation)-1]
	}
}

package dfs

import (
	"math"
)

// Result 用于存储最小费用
type Result struct {
	minCost int
}

// NewResult 创建一个新的 Result 实例，并初始化 minCost 为一个较大值
func NewResult() *Result {
	return &Result{
		minCost: math.MaxInt32,
	}
}

// minCost 计算访问所有城市的最小费用
func minCost(n int, roads [][]int) int {
	graph := constructGraph(roads, n)
	visited := make(map[int]bool)
	result := NewResult()
	visited[1] = true

	travel(1, n, visited, 0, graph, result)

	return result.minCost
}

// dfs 深度优先搜索遍历城市
func travel(
	city int,
	n int,
	visited map[int]bool,
	cost int,
	graph [][]int,
	result *Result) {

	// 如果所有城市都已访问，更新最小费用
	if len(visited) == n {
		if cost < result.minCost {
			result.minCost = cost
		}
		return
	}

	for i := 1; i < len(graph[city]); i++ {
		if visited[i] {
			continue
		}
		visited[i] = true
		travel(i, n, visited, cost+graph[city][i], graph, result)
		delete(visited, i)
	}
}

// constructGraph 构造图的邻接矩阵
func constructGraph(roads [][]int, n int) [][]int {
	graph := make([][]int, n+1)
	for i := range graph {
		graph[i] = make([]int, n+1)
		for j := range graph[i] {
			graph[i][j] = math.MaxInt32
		}
	}

	for _, road := range roads {
		a, b, c := road[0], road[1], road[2]
		graph[a][b] = min(graph[a][b], c)
		graph[b][a] = min(graph[b][a], c)
	}

	return graph
}

// min 返回两个整数中的较小值
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

// 0 .... i-1 i ..... -1 city
// 比较 (i-1,i) + (-1,city) 和 （i-1,-1) + (i,city)
// 相当于中间部分(i,-1)翻转
func hasBetterPath(graph [][]int, path []int, city int) bool {
	pathLength := len(path)
	for i := 1; i < pathLength; i++ {
		path_i_1 := path[i-1]
		path_i := path[i]
		path_last := path[pathLength-1]

		if graph[path_i_1][path_i]+graph[path_last][city] >
			graph[path_i_1][path_last]+graph[path_i][city] {
			return true
		}
	}
	return false
}

package dfs

import "math"

type Result2 struct {
	minCost int
}

func NewResult2() *Result {
	return &Result{minCost: 1000000}
}

func minCost2(n int, roads [][]int) int {
	graph := constructGraph(roads, n)
	visited := make(map[int]bool)
	path := []int{1}
	result := NewResult()
	visited[1] = true

	travel2(1, n, path, visited, 0, graph, result)

	return result.minCost
}

func travel2(city int, n int, path []int, visited map[int]bool, cost int, graph [][]int, result *Result) {
	if len(visited) == n {
		result.minCost = int(math.Min(float64(result.minCost), float64(cost)))
		return
	}

	for i := 1; i < len(graph[city]); i++ {
		if visited[i] {
			continue
		}
		if hasBetterPath(graph, path, i) {
			continue
		}
		visited[i] = true
		path = append(path, i)
		travel2(i, n, path, visited, cost+graph[city][i], graph, result)
		path = path[:len(path)-1]
		visited[i] = false
	}
}

func constructGraph2(roads [][]int, n int) [][]int {
	graph := make([][]int, n+1)
	for i := range graph {
		graph[i] = make([]int, n+1)
		for j := range graph[i] {
			graph[i][j] = 100000
		}
	}

	for _, road := range roads {
		a, b, c := road[0], road[1], road[2]
		if graph[a][b] > c {
			graph[a][b] = c
		}
		if graph[b][a] > c {
			graph[b][a] = c
		}
	}

	return graph
}

func hasBetterPath(graph [][]int, path []int, city int) bool {
	pathLength := len(path)
	for i := 1; i < pathLength; i++ {
		path_i_1 := path[i-1]
		path_i := path[i]
		path_last := path[pathLength-1]

		if graph[path_i_1][path_i]+graph[path_last][city] >
			graph[path_i_1][path_last]+graph[path_i][city] {
			return true
		}
	}
	return false
}