आलसी यात्राएँ
दो दोस्त अपनी ऊर्जा को लेकर इतने सावधान हैं कि उन्होंने एक स्थान से दूसरे स्थान तक जाने में लगने वाली कुल ऊर्जा का हिसाब लगा लिया है। इस हिसाब से, एक दोस्त को किसी स्थान से उसके पड़ोसी स्थान तक जाने में
A ऊर्जा खर्च करनी होगी, जबकि दूसरे दोस्त को वही दूरी तय करने में B ऊर्जा की आवश्यकता होगी।लेकिन उनके पास एक तरकीब भी है। अगर दोनों दोस्त किसी एक ही स्थान पर मौजूद हों, तो उनमें से एक दूसरे को उठा सकता है और इस तरह अगले स्थान तक साथ जाने में
A + B की बजाय C ऊर्जा लगेगी। ध्यान रखें कि C की मात्रा हमेशा A + B से कम ही हो, ऐसा ज़रूरी नहीं है, इसलिए किसी दोस्त को उठाकर चलना हर बार फायदेमंद साबित नहीं होगा।पहला दोस्त स्थान 1 से शुरू करता है, जबकि दूसरा दोस्त स्थान 2 से। दोनों को किसी तरह स्थान
n तक पहुँचना है और कोशिश है कि कुल ऊर्जा ख़र्च कम से कम हो। क्या आप बता सकते हैं कि उन्हें स्थान n तक पहुँचने में कम से कम कितनी कुल ऊर्जा की आवश्यकता पड़ेगी?Input
इनपुट की पहली पंक्ति में 3 पूर्णांक
A, B, और C (1 ≤ A, B, C ≤ 50 000) होते हैं।अगली पंक्ति में 2 पूर्णांक
n और e (1 ≤ n, e ≤ 100 000) होते हैं, जो स्थानों की कुल संख्या और स्थानों के बीच आने-जाने के कनेक्शनों की संख्या दर्शाते हैं।इसके बाद की अगली
e पंक्तियों में हर पंक्ति में दो पूर्णांक और (1 ≤ ≤ n) दिए होते हैं, जो दर्शाते हैं कि ये दोनों स्थान आपस में जुड़े हुए हैं।Output
कार्यक्रम को सबसे कम कुल ऊर्जा को प्रदर्शित करना चाहिए, जो उन्हें
n-वें स्थान तक पहुँचने में लगेगी।Examples
इनपुट | आउटपुट |
4 4 5
8 8
1 4
2 3
3 4
4 7
2 5
5 6
6 8
7 8 | 22 |
Explanation
पहला दोस्त: 1 → 4 ⇒ 4
दूसरा दोस्त: 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