Caminatas Perezosas
Dos amigos están tan pendientes de su energía que han calculado cuánta gastan al caminar de una ubicación a otra. Así, uno de ellos sabe que gastará
A de energía para moverse de una ubicación a una ubicación vecina, mientras que el segundo amigo gastará B de energía por hacer lo mismo.Sin embargo, tienen un truco: si ambos se encuentran en la misma ubicación, uno puede cargar al otro gastando
C de energía en vez de A+B si ambos caminaran al siguiente lugar. Es importante señalar que C no siempre es menor que A+B, por lo que llevar al otro a cuestas podría no ser siempre la opción más eficiente en términos de energía.El primer amigo comienza en la ubicación 1, y el segundo amigo en la ubicación 2. Ambos necesitan llegar a la ubicación
n gastando la menor cantidad de energía posible. ¿Puedes ayudarlos a determinar la mínima energía total necesaria para que ambos lleguen a la ubicación n?Entrada
La primera línea de la entrada contiene 3 enteros
A, B y C (1 ≤ A, B, C ≤ 50 000).La siguiente línea contiene 2 enteros
n y e (1 ≤ n, e ≤ 100 000), que representan la cantidad de ubicaciones y la cantidad de conexiones.Las siguientes
e líneas describen las conexiones entre ubicaciones, cada una representada por un par de enteros y (1 ≤ ≤ n), lo que indica que ambas ubicaciones están directamente conectadas.Salida
El programa debe imprimir la energía total mínima requerida para que ambos lleguen a la ubicación
n.Ejemplos
Entrada | Salida |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Explicación
Amigo 1: 1 → 4 ⇒ 4
Amigo 2: 2 → 3 → 4 ⇒ 8
Juntos: 4 → 7 → 8 ⇒ 10
En total: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB