Problem
Su Majestad el Rey Bubei II deseaba viajar por sus dominios. Al mismo tiempo, la ruta tiene los siguientes deseos:
1) la ruta debe tomar el menor tiempo posible (el tiempo real es algo muy valioso y debe protegerse);
2) la ruta debe incluir todos los asentamientos exactamente una vez (si el rey pierde un asentamiento, entonces sus habitantes se indignarán por la falta de atención real y dejarán de pagar impuestos; si el rey visita un asentamiento más de una vez, entonces los habitantes del resto los artículos de los asentamientos también estarán indignados)
3) la ruta debe comenzar y terminar en la capital del estado (habiendo recorrido sus posesiones, el rey debe ponerse inmediatamente manos a la obra). La capital se incluye en la ruta exactamente 2 veces: como punto de partida y como destino, no puede ser un asentamiento intermedio de la ruta.
Escriba un programa que utilice el mapa de carreteras del reino para encontrar dicha ruta o determine que es imposible cumplir con todos los requisitos.
Entrada
primero ingresa el número N (natural, no excede 10) – el número de asentamientos en el reino. Luego sigue N líneas de N números en cada – tiempo de viaje entre asentamientos (el tiempo es un número entero no negativo, no excede 500; si el tiempo = 0, esto significa que no hay forma entre algunos asentamientos). El Asentamiento No. 1 es la capital del estado.
Impresión
imprima el menor tiempo total que Su Majestad empleará en un desvío alrededor de sus dominios, o el número -1 si es imposible construir una ruta con las propiedades dadas.
Ejemplos
| # |
Entrada |
Salida |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |