En ومهرجان الفطيرة
Problem
اليوم ، تستضيف قلعة Aisne مهرجان الفطائر الذي تشارك فيه n مخابز ، لكل منها رقم فريد خاص به من 1 إلى n.
ترتبط بعض المخابز بطرق ذات اتجاهين ، ولكن بطريقة إذا كان من الممكن السير من المخبز 1 إلى المخبز j ، فهناك طريق واحد بالضبط بينهما.
عندما يأكل En الفطائر في المخبز الأول ، يحصل على ملذات
i . وإذا مرت على طول الطريق بين بعض المخابز ذات الأرقام v و u ، فإن رائحة الفطائر اللذيذة تجلب المتعة C
v، u .
لا تريد En الذهاب إلى كل مخبز أكثر من مرة (قد لا يذهب البعض على الإطلاق) ، لكنها تريد تحقيق أقصى استفادة من المهرجان.
سيبدأ من أحد الأفران ولن يعبر بينهما إلا بالطرق الموجودة.
ساعد En في تحديد أقصى قدر ممكن من المتعة التي يمكن أن يحصل عليها.
الإدخال:
يحتوي السطر الأول على الرقم n (1 & lt؛ = n & lt؛ = 50000) - عدد المخابز ، والرقم k - عدد الطرق الموجودة بين المخابز.
يحتوي السطر الثاني على عدد n من الأرقام A i (0 & lt؛ = A i & lt؛ = 10000) - متعة الفطائر في المخبز الأول.
ثم تتبع خطوط k ، كل منها يحتوي على 3 أرقام v ، u ، C (1 & lt ؛ = v ، u & lt ؛ = n ؛ v & ne ؛ u ؛ 0 & lt ؛ = C & lt ؛ = 10000) ، مما يعني أن هناك طريقًا بين مخابز مرقمة v و u ، والرائحة على هذا الطريق تجلب المتعة.
الإخراج:
طباعة رقم واحد - أقصى قدر ممكن من الرضا.
أمثلة:
نبسب ؛
<الجسم>
| إدخال |
الإخراج |
2 1
1 1
1 2 1
| 3 |
8 7
1 5 4 6 10 1 2 2
1 2 1
2 3 10
2 4 1
4 5 1
4 6 2
6 7 2
6 8 3
| 37 |
التفسيرات:
في المثال الأول ، عليك أن تبدأ من المخبز الأول (علاج واحد) ، والمشي على طول الطريق بين المخبز الأول والثاني (علاج واحد) ، وزيارة المخبز الثاني (علاج واحد). المتعة الكاملة - 1 + 1 + 1 = 3.
في المثال الثاني ، عليك أن تبدأ من المخبز الخامس (10 ملذات) ، والمشي على طول الطريق بين المخبزين الخامس والرابع (متعة واحدة) ، وزيارة المخبز الرابع (6 ملذات) ، واتبع الطريق بين الرابع والثاني. مخبز (علاج واحد) ، قم بزيارة المخبز الثاني (5 حلويات) ، وقم بالسير على طول الطريق بين المخابز الثاني والثالث (10 حلويات) ، وقم بزيارة المخبز الثالث (4 حلويات). المتعة الكلية - 10 + 1 + 6 + 1 + 5 + 10 + 4 = 37.