結果

問題 No.5007 Steiner Space Travel
コンテスト
ユーザー ID 21712
提出日時 2025-01-29 03:39:57
言語 Go
(1.23.4)
結果
AC  
実行時間 232 ms / 1,000 ms
コード長 2,522 bytes
コンパイル時間 15,071 ms
コンパイル使用メモリ 249,440 KB
実行使用メモリ 6,820 KB
スコア 7,828,543
最終ジャッジ日時 2025-01-29 03:40:21
合計ジャッジ時間 19,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

package main

import . "fmt"

const ALPHA = 5

func dist(a,b []int, i int, c,d []int, j int) int {
	dx := a[i] - c[j]
	dy := b[i] - d[j]
	return dx*dx + dy*dy
}

func main() {
	var n, m int
	Scan(&n, &m)
	a := make([]int, n)
	b := make([]int, n)
	for i := range a {
		Scan(&a[i],&b[i])
	}
	c := make([]int, m+1)
	d := make([]int, m+1)
	for i := range c {
		c[i] = (i%3+1)*250
		d[i] = (i/3+1)*250
	}
	c[m/2] = c[m]
	d[m/2] = d[m]
	c = c[:m]
	d = d[:m]
	
	path := make([][][]int, n)
	for i := range path {
		path[i] = make([][]int, n)
		for j := range path[i] {
			path[i][j] = []int{ 1e9,-1,-1 }
		}
	}
	for i := 0; i < n; i++ {
		for j := i+1; j < n; j++ {
			if i == j {
				continue
			}
			best := ALPHA*ALPHA*dist(a,b,i,a,b,j)
			st1,st2 := -1,-1
			for x := 0; x < m; x++ {
				tmp := ALPHA*dist(a,b,i,c,d,x) +
					ALPHA*dist(c,d,x,a,b,j)
				if tmp < best {
					best,st1,st2 = tmp,x,-1
				}
			}
			for x := 0; x < m; x++ {
				for y := 0; y < m; y++ {
					if x == y {
						continue
					}
					tmp := ALPHA*dist(a,b,i,c,d,x)+
						dist(c,d,x,c,d,y) +
						ALPHA*dist(c,d,y,a,b,j)
					if tmp < best {
						best,st1,st2 = tmp,x,y
					}
				}
			}
			rt := []int{best,st1,st2}
			path[i][j] = rt
			path[j][i] = rt
		}
	}
	
	p := []int{0}
	for i := 0; i < n; i++ {
		p = append(p, (i+1)%n)
	}
	
	for cc := 0; cc < 100; cc++ {
		// 2-opt ?
		for i := 1; i < n; i++ {
			for j := i+1; j < n; j++ {
				s0 := path[p[i-1]][p[i]][0] +
					path[p[j]][p[j+1]][0]
				s1 := path[p[i-1]][p[j]][0] +
					path[p[i]][p[j+1]][0]
				if s1 < s0 {
					for f,e := i,j; f < e; f,e=f+1,e-1 {
						p[f],p[e] = p[e],p[f]
					}
				}
			}
		}
		// 3-opt ?
		for i := 1; i < n; i++ {
			for j := i+1; j < n; j++ {
				for k := j+2; k < n; k++ {
					s0 := path[p[i-1]][p[i]][0] +
						path[p[j]][p[j+1]][0] +
						path[p[k]][p[k+1]][0]
					s1 := path[p[i-1]][p[j]][0] +
						path[p[i]][p[k]][0] +
						path[p[j+1]][p[k+1]][0]
					if s1 < s0 {
						for f,e := i,j; f < e; f,e=f+1,e-1 {
							p[f],p[e] = p[e],p[f]
						}
						for f,e := j+1,k; f < e; f,e=f+1,e-1 {
							p[f],p[e] = p[e],p[f]
						}
						
					}
				}
			}
		}
	}
	
	t := []int{1}
	r := []int{1}
	for i := 0; i < n; i++ {
		rt := path[p[i]][p[i+1]]
		if rt[1] >= 0 {
			t = append(t, 2)
			r = append(r, rt[1]+1)
		}
		if rt[2] >= 0 {
			t = append(t, 2)
			r = append(r, rt[2]+1)
		}
		t = append(t, 1)
		r = append(r, p[i+1]+1)
	}
	
	for i := range c {
		Println(c[i], d[i])
	}
	Println(len(t))
	for i := range t {
		Println(t[i], r[i])
	}
	
}
0