Farmer John cherche en bateau un trésor légendaire sur une des $N$ îles $(1 \le N \le 100)$ de Cowribbean Sea, numérotées $1,\ldots,N$.
La carte exige de partir de1, finir à $N$ et passer par $A_{1}$, $A_{2}$, ..., $A_{M}$, une suite de $M$ îles $(2 \le M \le 10,000)$, avant que le trésor apparaisse. Ces îles ou d’autres peuvent être visitées dans le désordre et répétées, mais $A_{i}$ doit apparaître dans l’ordre imposé.
FJ veut éviter les pirates et connaît le danger $(0 \le danger \le 100,000)$ entre chaque paire. Le danger total est la somme de tous les chemins parcourus.
Trouvez la route la moins dangereuse au trésor satisfaisant la carte.
Entrée
- Ligne1 : deux entiers séparés par un espace, $N$ et $M$.
- Lignes $2,\ldots,M+1$ : ligne $i+1$ donne la $i_{th}$ île obligatoire par un entier $A_{i}$.
- Lignes $M+2,\ldots,N+M+1$ : ligne $i+M+1$ contient $N$ entiers séparés par un espace, dangers de $i$ vers1, 2, ..., $N$. Le $i$-ième est toujours0.
Sortie
- Ligne1 : danger minimal pour obtenir le trésor.
Exemples
Entrée 1
3 4 1 2 1 3 0 5 1 5 0 2 1 2 0
Sortie 1
7
Remarque
3 îles,4 visites :1, 2, encore1, puis3. Les chemins(1,2), (2,3), (3,1) et inverses valent5, 2, 1.
La route1, 3, 2, 3, 1, 3 coûte7 et contient1, 2, 1, 3. On évite1–2, trop dangereux.
Auteur du problème : Jeffrey Wang, 2007