El Sr. X tiene que entregar software a N clientes. Desde la oficina, visitará a todos los clientes y luego regresará a su oficina. Cada ubicación de la oficina y de los clientes se da en forma de coordenadas enteras (x, y) (-1<x<500, -1<y<500). La distancia entre dos ubicaciones arbitrarias (x1, y1) y (x2, y2) se calcula mediante |x1-x2| + |y1-y2|, donde |x| denota el valor absoluto de x; por ejemplo, |3|=|-3|=3. Las ubicaciones de la oficina y los clientes son todas distintas. Debe planificar una forma óptima de visitar a todos los N clientes y regresar a su oficina.
Se le dan las ubicaciones de la oficina y los clientes; el número de clientes está en el rango de 1 a 100. Escriba un programa que, comenzando en la oficina, encuentre el camino más corto visitando a todos los clientes y regresando a su oficina. Su programa solo tiene que informar la distancia de un (el) camino más corto.
[Restricciones]
1<N<100. Cada ubicación (x, y) está en una cuadrícula delimitada, -1<x<500, -1<y<500 y x, y son números enteros.
[Entrada]
Cada caso de prueba consta de dos líneas; la primera línea tiene N, el número de clientes y la siguiente línea enumera las ubicaciones de la oficina y los clientes en secuencia. Cada ubicación consta de las coordenadas (x, y), que se representa por ‘x y’.
[Salida]
Cada línea genera la distancia de un (el) camino más corto. Cada línea parece ‘#x respuesta’ donde x es el índice de un caso de prueba. ‘#x’ y ‘respuesta’ están separados por un espacio.
Ejemplos:
Input : In the first test case, the locations of the office are (0, 0) and the locations of the customers are (70, 40), (30, 10), (10, 5), (90, 70), (50, 20). 5 (Starting test case #1) 0 0 70 40 30 10 10 5 90 70 50 20 Output : #1 320
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA