Problem
Il y a N villes dans le pays, dont certaines sont reliées par des routes. Il faut un plein d'essence pour rouler sur une route. Dans chaque ville, un réservoir d'essence a un coût différent. Vous devez vous rendre de la première ville à la nième en dépensant le moins d'argent possible. Vous ne pouvez pas acheter d'essence pour une utilisation future.
Entrée
La première ligne contient le nombre N (1≤N≤100), la ligne suivante contient N nombres, dont le i-ième précise le coût de l'essence dans la i-ième ville (ce sont des entiers de 0 à 100 ). Vient ensuite le nombre M – le nombre de routes dans le pays, suivi d'une description des routes elles-mêmes. Chaque route est donnée par deux nombres – les numéros des villes qu'il relie. Toutes les routes sont à double sens (c'est-à-dire qu'elles peuvent être conduites dans un sens et dans l'autre), il n'y a toujours pas plus d'une route entre deux villes, il n'y a pas de routes menant de la ville à elle-même.
Sortie
Requis pour générer un seul numéro – le coût total du trajet ou -1 s'il est impossible de s'y rendre.
Exemples
| # |
Entrée |
Sortie |
| 1 |
5
3 6 1 7 6
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
3 |