提出 #51538989

---

ソースコード 拡げる

package main

import (
	"bufio"
	"fmt"
	"math"
	"math/rand"
	"os"
	"strconv"
	"strings"
	"time"
)

func main() {
	n := readInt()
	XY := make([][2]int, n)
	for i := 0; i < n; i++ {
		scanIntVariables(&XY[i][0], &XY[i][1])
	}
	D := make([][]float64, n)
	for i := 0; i < n; i++ {
		D[i] = make([]float64, n)
		for j := 0; j < n; j++ {
			D[i][j] = math.Sqrt(float64((XY[i][0]-XY[j][0])*(XY[i][0]-XY[j][0]) + (XY[i][1]-XY[j][1])*(XY[i][1]-XY[j][1])))
		}
	}
	arr := make([]int, n)
	for i := 0; i < n; i++ {
		arr[i] = i
	}
	s := time.Now()
	ans := math.Inf(1)
	for {
		rand.Shuffle(n, func(i, j int) {
			arr[i], arr[j] = arr[j], arr[i]
		})
		tmp := 0.0
		for i := 0; i < n; i++ {
			tmp += D[arr[i]][arr[(i+1)%n]]
		}
		ans = min(ans, tmp)
		if time.Since(s).Milliseconds() > 1980 {
			break
		}
	}
	writeLine(ans)
}

func sum[T int | float64](arr ...T) T {
	sum := arr[0]
	for i := 1; i < len(arr); i++ {
		sum += arr[i]
	}
	return sum
}

func pow(x, n int) int {
	res := 1
	for n > 0 {
		if n&1 == 1 {
			res = res * x
		}
		x = x * x
		n >>= 1
	}
	return res
}

func lcm(a, b int) int {
	return a / gcd(a, b) * b
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func abs[T int | float64](x T) T {
	if x < 0 {
		return -x
	}
	return x
}

func min[T int | float64](arr ...T) T {
	min := arr[0]
	for _, v := range arr {
		if v < min {
			min = v
		}
	}
	return min
}

func max[T int | float64](arr ...T) T {
	max := arr[0]
	for _, v := range arr {
		if v > max {
			max = v
		}
	}
	return max
}

func ceilDiv(a, b int) int {
	if b < 0 {
		return ceilDiv(-a, -b)
	}
	if a < 0 {
		return a / b
	}
	return (a + b - 1) / b
}

func floorDiv(a, b int) int {
	if b < 0 {
		return floorDiv(-a, -b)
	}
	return (a - positiveMod(a, b)) / b
}

func positiveMod(a, b int) int {
	return (a%b + b) % b
}

var _stdInReader = bufio.NewReader(os.Stdin)

func readLine() string {
	line, _ := _stdInReader.ReadString('\n')
	return strings.TrimSpace(line)
}

func readString() string {
	return readLine()
}

func readInt() int {
	strs := readString()
	num, _ := strconv.Atoi(strs)
	return num
}

func readLong() int64 {
	strs := readString()
	num, _ := strconv.ParseInt(strs, 10, 64)
	return num
}

func readStrings() []string {
	line := readLine()
	return strings.Split(line, " ")
}

func readInts() []int {
	strs := readStrings()
	arr := make([]int, len(strs))
	for i := 0; i < len(strs); i++ {
		arr[i], _ = strconv.Atoi(strs[i])
	}
	return arr
}

func readLongs() []int64 {
	strs := readStrings()
	arr := make([]int64, len(strs))
	for i := 0; i < len(strs); i++ {
		arr[i], _ = strconv.ParseInt(strs[i], 10, 64)
	}
	return arr
}

func readDoubles() []float64 {
	strs := readStrings()
	arr := make([]float64, len(strs))
	for i := 0; i < len(strs); i++ {
		arr[i], _ = strconv.ParseFloat(strs[i], 64)
	}
	return arr
}

func scanStringVariables(args ...*string) {
	n := len(args)
	scanned := 0
	for n > scanned {
		inputSlice := readStrings()
		m := len(inputSlice)
		if m == 0 || m > n-scanned {
			fmt.Print("Something wrong in scanStringVariables !!!")
			return
		}
		for i := 0; i < m; i++ {
			*args[i+scanned] = inputSlice[i]
		}
		scanned += m
	}
}

func scanIntVariables(args ...*int) {
	n := len(args)
	scanned := 0
	for n > scanned {
		inputSlice := readInts()
		m := len(inputSlice)
		if m == 0 || m > n-scanned {
			fmt.Printf("m %d n %d scanned %d. ", m, n, scanned)
			fmt.Print("Something wrong in scanIntVariables !!!")
			return
		}
		for i := 0; i < m; i++ {
			*args[i+scanned] = inputSlice[i]
		}
		scanned += m
	}
}

func scanLongVariables(args ...*int64) {
	n := len(args)
	scanned := 0
	for n > scanned {
		inputSlice := readLongs()
		m := len(inputSlice)
		if m == 0 || m > n-scanned {
			fmt.Print("Something wrong in scanIntVariables !!!")
			return
		}
		for i := 0; i < m; i++ {
			*args[i+scanned] = inputSlice[i]
		}
		scanned += m
	}
}

func write(arg ...interface{})                 { fmt.Print(arg...) }
func writeLine(arg ...interface{})             { fmt.Println(arg...) }
func writeFormat(f string, arg ...interface{}) { fmt.Printf(f, arg...) }

提出情報

ジャッジ結果