Problem
Seine Majestät König Bubei Zweitens wollte sein Eigentum bewegen. Gleichzeitig werden folgende Wünsche auf die Route geäußert:
(1) Die Route sollte möglichst kurze Zeit dauern (die Queen ' s Zeit ist sehr wertvoll und muss erhalten werden);
(2) Die Route sollte alle Siedlungen auf einer einmaligen Basis umfassen (wenn der König eine Ortschaft vermisst, werden seine Bewohner durch königliche Unwissenheit wiederverwertet und Steuern aufgehalten; wenn der König mehr als einmal reist, werden auch die Bewohner der übrigen Siedlungen empört sein)
(3) Die Route sollte in der Hauptstadt des Staates beginnen und enden (auf der Landung muss der König sofort beginnen). Das Kapital betritt die Strecke genau 2 mal: Als Ausgangspunkt und als Ziel kann es keine Zwischenabrechnung der Strecke sein.
Schreiben Sie ein Programm, das nach dem Queen ' s Road Scheme eine solche Route findet oder bestimmt, dass alle Anforderungen nicht erfüllt werden können.
EingangsdatenErstens ist die Zahl der N (natürlich, nicht mehr als 10) die Zahl der Gemeinden des Königreichs. Die N-Linie auf den jeweils folgenden N-Zahlen ist die Zeit zwischen den menschlichen Siedlungen (die Zeit ist die ganze vernachlässigbare Zahl, nicht mehr als 500; wenn Zeit = 0, dann bedeutet das, dass es keinen Weg zwischen den menschlichen Siedlungen gibt). Die menschliche Siedlung Nr. 1 ist die Hauptstadt des Staates.
AusgangsdatenNehmen Sie die kürzeste Zeit, die Seine Majestät für die Umgehung seines Besitzes oder der Zahl ausgeben wird, wenn es nicht möglich ist, einen Weg mit einer bestimmten Eigenschaft zu bauen.
Beispiele
| Nein | Eingangsdaten | Ausgangsdaten |
|---|
| 1 | 1
0) | 0) |
| 2 | 2
1
1 0 | 2 |
| 3 | 2
0 85
85 0 | ANHANG |