Problem
Sua Majestade o Rei Bubei II desejava viajar por seus domínios. Ao mesmo tempo, a rota tem os seguintes desejos:
1) o percurso deve levar o menor tempo possível (tempo real – é uma coisa muito valiosa e deve ser protegida);
2) a rota deve incluir todos os assentamentos exatamente uma vez (se o rei perder um assentamento, seus habitantes ficarão indignados com a desatenção real e pararão de pagar impostos; se o rei visitar um assentamento mais de uma vez, os habitantes do restante itens de assentamentos também ficarão indignados)
3) o percurso deve começar e terminar na capital do estado (tendo percorrido seus bens, o rei deve imediatamente começar a trabalhar). A capital é incluída na rota exatamente 2 vezes: como ponto de partida e como destino, não pode ser um assentamento intermediário da rota.
Escreva um programa que use o roteiro do reino para encontrar tal rota ou determine que é impossível cumprir todos os requisitos.
Entrada
primeiro digite o número N (natural, não exceda 10) – o número de assentamentos no reino. Em seguida, segue N linhas de N números em cada – tempo de viagem entre assentamentos (tempo - é um número inteiro não negativo, não excede 500; se tempo = 0, isso significa que não há caminho entre alguns assentamentos). O assentamento nº 1 é a capital do estado.
Impressão
imprima o menor tempo total que Sua Majestade gastará em um desvio em torno de seus domínios, ou o número -1 se for impossível construir uma rota com as propriedades dadas.
Exemplos
| # |
Entrada |
Saída |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |