Submission #17524559

Source Code Expand

(N,),*XYZ = $<.map{|ln| ln.split.map(&:to_i) }

C = XYZ.map{|a,b,c|
	XYZ.map{|p,q,r|
		(p-a).abs+(q-b).abs+[0,r-c].max
	}
}

CV = Array.new(1<<N-1){ [Float::INFINITY]*N }
CV[0][0] = 0

(1<<N-1).times{|v|
	N.times{|f|
		c,cf,f2 = CV[v|1<<f-1],CV[v][f],C[f]
		N.times{|t|
			c[t] = cf+f2[t] if cf+f2[t] < c[t]
		} if cf < CV[-1][0]
	}
}

p CV[-1][0]

Submission Info

Submission Time
Task E - Traveling Salesman among Aerial Cities
User ds14050
Language Ruby (2.7.1)
Score 500
Code Size 369 Byte
Status AC
Exec Time 1283 ms
Memory 28416 KiB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 500 / 500
Status
AC × 3
AC × 23
Set Name Test Cases
Sample sample_01.txt, sample_02.txt, sample_03.txt
All random_01.txt, random_02.txt, random_03.txt, random_04.txt, random_05.txt, random_06.txt, random_07.txt, random_08.txt, random_09.txt, random_10.txt, random_11.txt, random_12.txt, random_13.txt, random_14.txt, random_15.txt, random_16.txt, random_17.txt, random_18.txt, random_19.txt, random_20.txt, sample_01.txt, sample_02.txt, sample_03.txt
Case Name Status Exec Time Memory
random_01.txt AC 1229 ms 28300 KiB
random_02.txt AC 63 ms 14064 KiB
random_03.txt AC 1233 ms 28416 KiB
random_04.txt AC 1248 ms 28404 KiB
random_05.txt AC 1238 ms 28252 KiB
random_06.txt AC 57 ms 14272 KiB
random_07.txt AC 1233 ms 28416 KiB
random_08.txt AC 167 ms 15264 KiB
random_09.txt AC 1249 ms 28304 KiB
random_10.txt AC 59 ms 14072 KiB
random_11.txt AC 1229 ms 28096 KiB
random_12.txt AC 63 ms 14120 KiB
random_13.txt AC 1271 ms 28396 KiB
random_14.txt AC 60 ms 14124 KiB
random_15.txt AC 1218 ms 28076 KiB
random_16.txt AC 108 ms 14468 KiB
random_17.txt AC 1283 ms 28136 KiB
random_18.txt AC 105 ms 14460 KiB
random_19.txt AC 1234 ms 28260 KiB
random_20.txt AC 167 ms 15148 KiB
sample_01.txt AC 62 ms 14324 KiB
sample_02.txt AC 59 ms 14264 KiB
sample_03.txt AC 1216 ms 28200 KiB