結果

問題 No.5007 Steiner Space Travel
ユーザー ID 21712ID 21712
提出日時 2025-01-29 03:55:34
言語 Go
(1.23.4)
結果
AC  
実行時間 30 ms / 1,000 ms
コード長 3,034 bytes
コンパイル時間 15,181 ms
コンパイル使用メモリ 243,196 KB
実行使用メモリ 5,248 KB
スコア 7,626,946
最終ジャッジ日時 2025-01-29 03:55:53
合計ジャッジ時間 16,208 ms
ジャッジサーバーID
(参考情報)
judge2 / judge4
純コード判定しない問題か言語
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

package main
import . "fmt"
import "math/rand"
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)
}
calc := func() int {
sc := 0
for i := 0; i < n; i++ {
sc += path[p[i]][p[i+1]][0]
}
return sc
}
bestSc := calc()
bestP := make([]int, len(p))
copy(bestP, p)
for kk := 0; kk < 10; kk++ {
for cc, changed := 0, true; changed && cc < 50; cc, changed = cc+1, false {
// 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]
}
changed = true
}
}
}
// 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]
}
changed = true
}
}
}
}
}
if sc := calc(); sc < bestSc {
bestSc = sc
copy(bestP, p)
}
rand.Shuffle(n-1, func(i, j int) {
p[i+1],p[j+1] = p[j+1],p[i+1]
})
}
p = bestP
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])
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0