Submission #51642735

---

Source Code Expand

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"

	"github.com/liyue201/gostl/ds/priorityqueue"
)

type Edge struct {
	from int
	to   int
	cost float64
}

type Node struct {
	value int
	prev  *Node
	next  *Node
}

type UniqueDoublyLinkedList struct {
	head     *Node
	tail     *Node
	accessor map[int]*Node
	len      int
}

func newLinkedList() *UniqueDoublyLinkedList {
	return &UniqueDoublyLinkedList{
		head:     nil,
		tail:     nil,
		accessor: make(map[int]*Node),
	}
}

func (ll *UniqueDoublyLinkedList) add(value int) {
	node := &Node{value: value}
	if ll.head == nil {
		ll.head = node
		ll.tail = node
	} else {
		ll.tail.next = node
		node.prev = ll.tail
		ll.tail = node
	}
	ll.accessor[value] = node
	ll.len++
}

func (ll *UniqueDoublyLinkedList) insertAfter(preValue int, value int) {
	preNode := ll.accessor[preValue]
	node := &Node{value: value}
	node.prev = preNode
	node.next = preNode.next
	if preNode == ll.tail {
		ll.tail = node
	} else {
		preNode.next.prev = node
	}
	preNode.next = node
	ll.len++
	ll.accessor[value] = node
}

func (ll *UniqueDoublyLinkedList) has(value int) bool {
	_, ok := ll.accessor[value]
	return ok
}

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])))
		}
	}
	G := make([][]Edge, n)
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			G[i] = append(G[i], Edge{i, j, D[i][j]})
		}
	}

	ans := math.Inf(1)
	for s := 0; s < n; s++ {
		res := 0.0
		nonVisited := make(map[int]bool)
		for i := 0; i < n; i++ {
			nonVisited[i] = true
		}
		pi := newLinkedList() // 部分巡回路
		v := s
		pi.add(v)
		delete(nonVisited, v)
		que := priorityqueue.New[Edge](func(a, b Edge) int {
			if a.cost < b.cost {
				return -1
			} else if a.cost > b.cost {
				return 1
			}
			return 0
		}) // 挿入する辺の候補
		for _, e := range G[v] {
			que.Push(e)
		}
		for !que.Empty() {
			e := que.Pop()
			if pi.has(e.to) {
				continue
			}
			if pi.len == 1 {
				res += e.cost
				pi.add(e.to)
			} else {
				u := pi.head
				minCost := math.Inf(1)
				minV := -1
				for u.next != nil {
					cost := D[u.value][e.to] + D[e.to][u.next.value] - D[u.value][u.next.value]
					if cost < minCost {
						minCost = cost
						minV = u.value
					}
					u = u.next
				}
				res += minCost
				pi.insertAfter(minV, e.to)
			}
			delete(nonVisited, e.to)
			v = e.to
			for u := range nonVisited {
				que.Push(G[v][u])
			}
		}
		res += D[pi.tail.value][s]
		ans = math.Min(ans, res)
	}

	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...) }

Submission Info

Judge Result