Farmer John a acheté un terrain dans les Caraïbes et veut élever des vaches laitières sur une grande ferme composée d’îles. Fidèle à ses habitudes, il veut clôturer toutes les îles.

Chaque île est un polygone. Il clôture un côté à la fois, entre sommets consécutifs, en tournant dans le sens horaire. Pour toutes les clôturer, il doit parfois rejoindre les autres en bateau.

Il peut commencer à tout sommet et, à tout sommet rencontré, partir vers un sommet d’une autre île, la clôturer entièrement, puis revenir IMMÉDIATEMENT au même sommet initial par le même chemin. Chaque trajet en bateau a un coût donné par une matrice.

Les îles sont décrites par $N$ $(3 \le N \le 500)$ paires de sommets $V1$,$V2$ $(1 \le V1 \le N; 1 \le V2 \le N)$ ; vous devez les assembler en îles. Les sommets sont numérotés $1,\ldots,N$.

Les coûts en bateau entre sommets sont donnés par une matrice symétrique dont les éléments sont dans $0,\ldots,1000$.

Quel est le coût minimal pour clôturer toutes les îles ?

Entrée

• Ligne $1$ : entier $N$.

• Lignes $2,\ldots,N+1$ : chacune décrit un bord avec les entiers $V1$, $V2$ séparés par un espace.

• Lignes $N+2,\ldots,2\times N+1$ : la ligne $i-N-1$ contient $N$ entiers décrivant la ligne $i$ de la matrice : $Row_{i}$.

Sortie

• Ligne $1$ : entier, coût minimal de construction de la clôture.

Exemples

Entrée 1

12
1 7
7 3
3 6
6 10
10 1
2 12
2 9
8 9
8 12
11 5
5 4
11 4
0 15 9 20 25 8 10 13 17 8 8 7
15 0 12 12 10 10 8 15 15 8 8 9
9 12 0 25 20 18 16 14 13 7 12 12
20 12 25 0 8 13 14 15 15 10 10 10
25 10 20 8 0 16 20 18 17 18 9 11
8 10 18 13 16 0 10 9 11 10 8 12
10 8 16 14 20 10 0 18 20 6 16 15
13 15 14 15 18 9 18 0 5 12 12 13
17 15 13 15 17 11 20 5 0 22 8 10
8 8 7 10 18 10 6 12 22 0 11 12
8 8 12 10 9 8 16 12 8 11 0 9
7 9 12 10 11 12 15 13 10 12 9 0

Sortie 1

30

Remarque

  1        10            4
    xxxxxxx              x
   xxxxxxxxx            xxxx
7 xxxxxxxxxxx 6        xxxxxxx
 xxxxxxxxxxx       11 xxxxxxxxxx 5
  xxxxxxx
   xxx
  3         12 xxxxxxx 2
              xxxxxxxx
              xxxxxxxx
             xxxxxxxxx
             xxxxxxxxx
            xxxxxxxxxx
            xxxxxxxxxx
          8 xxxxxxxxxx 9

Les trois îles sont $\{1,7,3,6,10\}$, $\{4,5,11\}$ et $\{2,9,8,12\}$. La matrice donne les coûts ; par exemple $1$ vers $2$ coûte $15$.

Plusieurs solutions existent. FJ part de $3$, passe par $7$, s’arrête à $1$, rejoint $11$, puis $4,5,11$. Il revient à $1$, rejoint $12$, puis $2,9,8,12$. Enfin, il revient à $1$ et continue par $10,6,3,7$. L’aller-retour de $1$ à $11$ coûte $8 \times 2 = 16$, celui de $1$ à $12$ $7 \times 2 = 14$, soit $30$ au total.

Auteur du problème : Fatih Gelgi, 2008