Problem
Sa Majesté le Roi Bubei II souhaitait parcourir son domaine. En même temps, l'itinéraire a les souhaits suivants :
1) l'itinéraire doit prendre le moins de temps possible (l'heure royale - est une chose très précieuse et doit être protégée) ;
2) l'itinéraire doit inclure toutes les colonies exactement une fois (si le roi manque une colonie, ses habitants seront indignés par l'inattention royale et cesseront de payer des impôts ; si le roi visite une colonie plus d'une fois, alors les habitants du reste articles de colonies seront également indignés)
3) la route doit commencer et se terminer dans la capitale de l'État (après avoir fait le tour de ses possessions, le roi doit immédiatement se mettre au travail). La capitale est incluse dans l'itinéraire exactement 2 fois : en tant que point de départ et en tant que destination, elle ne peut pas être une localité intermédiaire de l'itinéraire.
Écrivez un programme qui utilise la carte routière du royaume pour trouver un tel itinéraire ou détermine qu'il est impossible de remplir toutes les conditions.
Entrée
entrez d'abord le nombre N (naturel, ne dépasse pas 10) – le nombre de colonies dans le royaume. Vient ensuite N lignes de N nombres dans chaque – le temps de trajet entre les localités (le temps – est un entier non négatif, ne dépasse pas 500 ; si le temps = 0, cela signifie qu'il n'y a pas de chemin entre certaines localités). La colonie n° 1 est la capitale de l'État.
Mentions légales
imprimer le moins de temps total que Sa Majesté consacrera à un détour autour de ses domaines, ou le nombre -1 s'il est impossible de construire un itinéraire avec les propriétés données.
Exemples
| # |
Entrée |
Sortie |
| 1 |
1
0 |
0 |
| 2 |
2
0 1
10 |
2 |
| 3 |
2
0 85
85 0 |
170 |