Ալարկոտ քայլեր
Երկու ընկեր այնքան են ուշադիր իրենց էներգիայի ծախսի նկատմամբ, որ հաշվարկել են, թե ինչքան էներգիա կծախսեն, երբ մի վայրից գնան հարակից վայր։ Այսպես, առաջին ընկերը տեղաշարժվելու համար ծախսում է
A էներգիա, իսկ երկրորդ ընկերը՝ B էներգիա։Սակայն նրանք կարող են կիրառել մի խորամանկություն. եթե երկուսն էլ նույն վայրում են, ապա նրանցից մեկը կարող է վերցնել մյուսին և միասին քայլել հաջորդ վայր, ծախսելով
C էներգիա։ Սա նշանակում է, որ երբ մեկ ընկերն անում է այդ տեղափոխումը, իրական էներգիական արժեքը կլինի C այն դեպքում, երբ երկուսով քայլեին, այն կաշխատեր A + B։ Դեռ պետք է նշել, որ C-ի արժեքը պարտադիր չէ, որ միշտ լինի A + B-ից փոքր, հետևաբար մեկի վրա մյուսի փոխադրումը միշտ չէ, որ ամենարդյունավետ տարբերակն է։Առաջին ընկերը սկսում է
1 վայրից, իսկ երկրորդ ընկերը՝ 2 վայրից։ Նրանք պետք է հասնեն n վայր և փորձեն ծախսել հնարավորինս քիչ ընդհանուր էներգիա։ Օգնում՞ եք որոշել նվազագույն ընդհանուր էներգիան, որն անհրաժեշտ է, որպեսզի նրանք հասնեն n-րդ վայր։Մուտք
Մուտքի առաջին տողում տրված են 3 ամբողջ թվեր
A, B և C (1 ≤ A, B, C ≤ 50 000):Հաջորդ տողում տրված են 2 ամբողջ թվեր
n և e (1 ≤ n, e ≤ 100 000), որտեղ n-ը վայրերի քանակն է, իսկ e-ն՝ կապերի քանակը:Հաջորդ
e տողերը περιέχουν կապերը վայրերի միջև, ներկայացված երկու ամբողջ թվերով և (1 ≤ ≤ n), որոնք ցույց են տալիս, թե տվյալ երկու վայրերը միմյանց հետ կապ ունեն։Ելք
Ծրագիրը պետք է տպի անհրաժեշտ նվազագույն ընդհանուր էներգիան, որպեսզի նրանք հասնեն
n-րդ վայր։Օրինակներ
Մուտք | Ելք |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Բացատրություն
Ընկեր 1: 1 → 4 ⇒ 4
Ընկեր 2: 2 → 3 → 4 ⇒ 8
Միասին: 4 → 7 → 8 ⇒ 10
Ընդհանուր առմամբ: 4 + 8 + 10 = 22
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB