Submission #17516238

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+[r-c,0].max
	}
}

NP = Array.new(N){ [Float::INFINITY]*2**N }
NP[0][1] = 0
(1<<N).times{|v|
	N.times{|f|
		c0,cf = NP[f][v],C[f]
		next if NP[0][-1] <= c0
		N.times{|t|
			c = c0+cf[t]
			NP[t][v|1<<f] = c if c < NP[t][v|1<<f]
		}
	}
}

p NP[0][-1]

Submission Info

Submission Time
Task E - Traveling Salesman among Aerial Cities
User ds14050
Language Ruby (2.7.1)
Score 500
Code Size 378 Byte
Status AC
Exec Time 1933 ms
Memory 31856 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 1895 ms 31648 KiB
random_02.txt AC 57 ms 14168 KiB
random_03.txt AC 1879 ms 31560 KiB
random_04.txt AC 1890 ms 31504 KiB
random_05.txt AC 1881 ms 31780 KiB
random_06.txt AC 58 ms 14088 KiB
random_07.txt AC 1877 ms 31644 KiB
random_08.txt AC 214 ms 16096 KiB
random_09.txt AC 1928 ms 31584 KiB
random_10.txt AC 61 ms 14256 KiB
random_11.txt AC 1897 ms 31672 KiB
random_12.txt AC 63 ms 14372 KiB
random_13.txt AC 1910 ms 31828 KiB
random_14.txt AC 57 ms 14112 KiB
random_15.txt AC 1885 ms 31608 KiB
random_16.txt AC 131 ms 14936 KiB
random_17.txt AC 1933 ms 31856 KiB
random_18.txt AC 129 ms 14920 KiB
random_19.txt AC 1895 ms 31720 KiB
random_20.txt AC 216 ms 16032 KiB
sample_01.txt AC 59 ms 14176 KiB
sample_02.txt AC 59 ms 14164 KiB
sample_03.txt AC 1872 ms 31856 KiB