Balades paresseuses
Deux amis font très attention à l’énergie qu’ils dépensent lorsqu’ils se déplacent d’un lieu à un autre. Ainsi, l’un sait qu’il dépensera
A unités d’énergie pour aller d’un emplacement à un emplacement voisin, tandis que l’autre dépensera B unités d’énergie pour la même chose.Cependant, ils disposent d’une astuce. S’ils se trouvent au même endroit, l’un peut porter l’autre et dépenser
C unités d’énergie au lieu de A+B s’ils avançaient tous les deux à pied vers l’emplacement suivant. Il est important de noter que la valeur de C n’est pas toujours inférieure à A+B, ce qui signifie que porter l’autre n’est pas forcément l’option la plus économe en énergie.Le premier ami commence à l’emplacement 1, tandis que le second ami commence à l’emplacement 2. Ils doivent tous les deux atteindre l’emplacement
n en dépensant le moins d’énergie possible. Pouvez-vous déterminer la quantité minimale d’énergie totale nécessaire pour atteindre l’emplacement n ?Entrée
La première ligne de l’entrée contient 3 entiers
A, B et C (1 ≤ A, B, C ≤ 50 000).La ligne suivante contient 2 entiers
n et e (1 ≤ n, e ≤ 100 000), qui représentent respectivement le nombre d’emplacements et le nombre de connexions.Les
e lignes suivantes décrivent les connexions entre les emplacements au moyen de paires d’entiers et (1 ≤ ≤ n), indiquant que ces deux emplacements sont reliés l’un à l’autre.Sortie
Le programme doit afficher la quantité minimale d’énergie totale nécessaire pour atteindre l’emplacement
n.Exemples
Entrée | Sortie |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Explication
Friend 1 : 1 → 4 ⇒ 4
Friend 2 : 2 → 3 → 4 ⇒ 8
Together : 4 → 7 → 8 ⇒ 10
In total : 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB