package main

import (
	"fmt"
	"math"
)

// Matriks jarak antar kota
var distanceMatrix = [][]int{
	{0, 20, 28, 7},
	{24, 0, 25, 8},
	{19, 22, 0, 19},
	{27, 25, 21, 0},
}

var n = len(distanceMatrix)
var bound = math.MaxInt64
var bestRoute []int

// Fungsi untuk menghitung estimasi biaya minimum untuk rute tersisa
func minimumPossibleCost(remainingCities []int, currentCity int) int {
	minCost := 0
	for _, city := range remainingCities {
		min := math.MaxInt64
		for _, nextCity := range remainingCities {
			if distanceMatrix[city][nextCity] < min {
				min = distanceMatrix[city][nextCity]
			}
		}
		minCost += min
	}
	return minCost
}

// Fungsi rekursif untuk mengimplementasikan algoritma Branch and Bound
func tspBranchAndBound(currentCity int, visitedCities []int, currentCost int) {
	// Jika semua kota telah dikunjungi
	if len(visitedCities) == n {
		// Tambahkan biaya untuk kembali ke kota awal
		totalCost := currentCost + distanceMatrix[currentCity][visitedCities[0]]
		if totalCost < bound {
			bound = totalCost
			bestRoute = append([]int(nil), visitedCities...)
			bestRoute = append(bestRoute, visitedCities[0])
		}
		return
	}

	// Iterasi untuk setiap kota yang belum dikunjungi
	for city := 0; city < n; city++ {
		alreadyVisited := false
		for _, v := range visitedCities {
			if v == city {
				alreadyVisited = true
				break
			}
		}

		if !alreadyVisited {
			newCost := currentCost + distanceMatrix[currentCity][city]

			remainingCities := []int{}
			for i := 0; i < n; i++ {
				if !contains(visitedCities, i) && i != city {
					remainingCities = append(remainingCities, i)
				}
			}

			if newCost+minimumPossibleCost(remainingCities, city) < bound {
				tspBranchAndBound(city, append(visitedCities, city), newCost)
			}
		}
	}
}

// Fungsi helper untuk memeriksa apakah suatu elemen ada dalam slice
func contains(slice []int, elem int) bool {
	for _, v := range slice {
		if v == elem {
			return true
		}
	}
	return false
}

func main() {
	// Memulai algoritma Branch and Bound dari kota pertama (index 0)
	tspBranchAndBound(0, []int{0}, 0)

	// Cetak rute terbaik dan biaya terendah
	fmt.Println("Rute Terbaik:", bestRoute)
	fmt.Println("Biaya Terendah:", bound)
}