Problem
Besi est situé sur un réseau de N (2≤N≤10
5) sommets étiquetés 1…N et 2N portails étiquetés 1…2N. Chaque portail relie deux sommets différents u et v (u≠v). Un ensemble de portails peut connecter une paire de sommets.
Chaque sommet v est adjacent à quatre portails différents. La liste des portails de v est donnée par pv=[p
v,1,p
v,2,p
v,3,p< sous>v ,4].
Votre position actuelle peut être représentée par une paire ordonnée (sommet actuel, portail actuel) ; c'est-à-dire une paire (v,p
v,i) où 1≤v≤N et 1≤i≤4. Vous pouvez utiliser l'une des opérations suivantes pour modifier votre position actuelle :
Modifiez le sommet actuel en vous déplaçant dans le portail actuel.
Changer de portail actuel. A chaque sommet, les deux premiers portails de la liste sont appariés et les deux derniers portails de la liste sont également appariés. Donc, si votre état actuel est (v,p
v,2), vous pouvez basculer pour utiliser le portail (v,p
v,1) et inversement. De même, si votre position actuelle est (v,p
v,3), vous pouvez passer au portail (v,p
v,4) et revenir. aucune autre commutation n'est autorisée (par exemple, vous ne pouvez pas passer du portail pv,2 au portail) p
v,4).
Il y a 4N états différents au total. Malheureusement, il se peut qu'aucun état ne soit accessible à partir de n'importe quel état par une séquence d'opérations données. Par conséquent, pour le coût des lunes cv (1≤c
v≤1000), vous pouvez réorganiser la liste des portails adjacents à v, dans l'ordre de votre choix. Après cela, les deux premiers portails de la liste sont combinés en une paire et les deux derniers portails en une autre paire.
Par exemple, si vous réorganisez les portails de v dans l'ordre [p
v,3,p
v,1,p
v,2, p
v,4], cela signifie. et si vous êtes au top v,
Si vous êtes dans le portail p
v,1, vous pouvez passer au portail p
v,3 et revenir
Si vous êtes dans le portail p
v,2, vous pouvez passer au portail p
v,4 et revenir
Vous ne pouvez plus passer du portail p
v,1 à p
v,2, ou du portail p
v,3 au portail p
v,4 et vice versa.
Calculez le nombre minimum de lunes nécessaires pour modifier le réseau de manière à rendre chaque état accessible depuis chaque état. Il est garanti que les données de test sont construites de telle manière qu'il existe au moins une façon de modifier le réseau de cette manière.
Entrée :
La première ligne contient N.
Chacune des N lignes suivantes décrit un sommet. La chaîne v+1 contient 5 entiers séparés par des espaces c
v,p
v,1,p
v,2,p
v ,3,p
v,4.
Il est garanti que pour chaque v tous les p
v,1,p
v,2,p
v,3,p
v, 4 sont distincts, et chaque portail apparaît dans les listes d'exactement deux sommets.
Sortie :
Une ligne contient le nombre minimum de lunes nécessaires pour modifier le réseau afin de rendre chaque état accessible depuis un autre état.
Exemples
| # |
Entrée |
Sortie |
Explication |
| 1 |
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5 |
13 |
Il suffit d'échanger les listes de sommets 1 et 4. Cela nécessite c1+c4=13 muns. Les permutations sont : p1=[1,9,4,8] et p4=[7,4,6,3]. |