Lazy Walks
Zwei Freunde achten sehr auf ihren Energieverbrauch und haben berechnet, wie viel Energie sie jeweils beim Gehen von einem Ort zum nächsten verbrauchen. Einer der beiden benötigt dafür
A Energie, während der andere B Energie aufwendet.Allerdings gibt es einen Trick: Wenn sich beide am selben Ort befinden, kann einer den anderen tragen und dabei
C Energie verbrauchen, anstatt dass jeder für sich läuft und zusammen A + B aufwenden würde. Es ist wichtig zu beachten, dass C nicht unbedingt immer kleiner als A + B ist. Das bedeutet, dass das Tragen des anderen nicht in jedem Fall die energieeffizientere Option darstellt.Der erste Freund startet an Ort 1, während der zweite Freund an Ort 2 beginnt. Beide sollen den Ort
n erreichen und dabei insgesamt möglichst wenig Energie verbrauchen. Kannst du helfen, die minimale Gesamtenergiemenge zu ermitteln, die notwendig ist, damit beide den Ort n erreichen?Eingabe
Die erste Zeile der Eingabe enthält 3 ganze Zahlen
A, B und C (1 ≤ A, B, C ≤ 50 000).Die nächste Zeile enthält 2 ganze Zahlen
n und e (1 ≤ n, e ≤ 100 000), also die Anzahl der Orte und die Anzahl der Verbindungen.Die darauffolgenden
e Zeilen enthalten die Verbindungen zwischen den Orten. Jede Verbindung wird durch ein Paar ganzzahliger Werte und (1 ≤ ≤ n) beschrieben, die bedeuten, dass die beiden Orte direkt miteinander verbunden sind.Ausgabe
Das Programm soll die minimal erforderliche Gesamtenergiemenge ausgeben, damit beide den
n-ten Ort erreichen können.Beispiele
Eingabe | Ausgabe |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Erklärung
Freund 1: 1 → 4 ⇒ 4
Freund 2: 2 → 3 → 4 ⇒ 8
Zusammen: 4 → 7 → 8 ⇒ 10
Insgesamt: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB