Problem
Sua Maestà il Re Bubei II desiderava viaggiare nel suo dominio. Allo stesso tempo, il percorso ha i seguenti desideri:
1) il percorso dovrebbe richiedere il minor tempo possibile (il tempo reale è una cosa molto preziosa e dovrebbe essere protetto);
2) il percorso deve includere tutti gli insediamenti esattamente una volta (se il re perde un insediamento, i suoi abitanti saranno oltraggiati dalla disattenzione reale e smetteranno di pagare le tasse; se il re visita un insediamento più di una volta, allora gli abitanti del restante anche gli elementi di liquidazione saranno indignati)
3) il percorso deve iniziare e terminare nella capitale dello stato (il re, dopo aver percorso i suoi possedimenti, deve mettersi subito al lavoro). Il capoluogo è compreso nel percorso esattamente 2 volte: come punto di partenza e come destinazione, non può essere un insediamento intermedio del percorso.
Scrivi un programma che utilizzi la mappa stradale del regno per trovare tale percorso o stabilisca che è impossibile soddisfare tutti i requisiti.
Inserimento
inserisci prima il numero N (naturale, non supera 10) – il numero di insediamenti nel regno. Quindi segue N righe di N numeri in ciascuna – tempo di viaggio tra gli insediamenti (tempo – è un numero intero non negativo, non supera 500; se tempo = 0, significa che non c'è modo tra alcuni insediamenti). L'insediamento n. 1 è la capitale dello stato.
Impressum
stampa il tempo totale minimo che Sua Maestà impiegherà per una deviazione intorno ai suoi domini, o il numero -1 se è impossibile costruire un percorso con le proprietà date.
Esempi
| # |
Input |
Uscita |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |