Passeggiate Pigre
Due amici sono estremamente attenti al proprio dispendio di energia e hanno calcolato quanta ne consumano per andare da un luogo a un altro. In particolare, uno dei due sa che impiega
A energia per spostarsi da una località a una località vicina, mentre l’altro amico sa che spenderà B energia per lo stesso tragitto.Tuttavia, esiste un piccolo trucco. Se entrambi gli amici si trovano nella stessa località, uno può trasportare l’altro impiegando
C energia al posto di A+B che avrebbero consumato camminando separatamente fino alla località successiva. È importante notare che C non è necessariamente minore di A+B, il che significa che portare l’altro in braccio non è sempre l’opzione più efficiente dal punto di vista energetico.Il primo amico parte dalla località 1, mentre il secondo parte dalla località 2. Entrambi devono arrivare alla località
n, spendendo il minimo di energia possibile. Riusciresti ad aiutarli a determinare la quantità minima di energia necessaria per arrivare alla località n?Input
La prima riga dell’input contiene 3 interi
A, B e C (1 ≤ A, B, C ≤ 50 000).La riga successiva contiene 2 interi
n e e (1 ≤ n, e ≤ 100 000), che indicano rispettivamente il numero di località e il numero di connessioni.Le successive
e righe descrivono le connessioni tra le località mediante una coppia di interi e (1 ≤ ≤ n), indicando che quelle due località sono collegate tra loro.Output
Il programma deve stampare l’energia totale minima necessaria affinché entrambi raggiungano la località
n.Esempi
Input | Output |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Spiegazione
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