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. De plus, vous disposez d'une bonbonne d'essence qui contient la même quantité de carburant qu'un réservoir d'essence.
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.
Dans chaque ville, vous pouvez remplir le réservoir, remplir le réservoir et le bidon, ou verser de l'essence du bidon dans le réservoir. Cela vous permet d'économiser de l'argent en achetant de l'essence dans les villes où c'est moins cher, mais le bidon ne suffit que pour un plein de réservoir !
Entrée
La première ligne contient le nombre N (1<=N<=100), la ligne suivante contient N nombres, dont le i-ième définit le coût de l'essence dans la i-ième ville (tous ceux-ci sont des nombres entiers de la plage 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 de l'itinéraire, ou -1 s'il est impossible d'y arriver.
Exemples
| # |
Entrée |
Sortie |
| 1 |
4
1 10 2 15
4
1 2
1 3
4 2
4 3
2 |