Module: برمجة الرسم البياني الديناميكي


Problem

5 /7


اختصار لـ DAG

Theory Click to read/hide

في الحلول التي تستخدم البرمجة الديناميكية ، يكون الترتيب الذي يتم به حساب الديناميكيات أمرًا مهمًا (من الضروري أن يتم حساب القيم التي تعتمد عليها القيمة الحالية من قبل).
لذلك ، إذا كان من الضروري استخدام البرمجة الديناميكية على الرسوم البيانية غير الدورية الموجهة ، فمن الضروري في البداية إنشاء فرز طوبولوجي للرسم البياني. ثم احسب الديناميكيات بالفرز عبر القمم بترتيب الفرز الطوبولوجي المركب (حسب المشكلة ، يمكن أن يكون ترتيب الاجتياز من المصادر إلى الأحواض أو العكس).
نبسب ؛
نبسب ؛

Problem

يتم إعطاء رسم بياني دائري مرجح. مطلوب للعثور على أقصر طريق فيه
من الرأس s إلى الرأس t.

الإدخال:
يحتوي السطر الأول من ملف الإدخال على أربعة أعداد صحيحة n و m و s و t - عدد الرؤوس ، وحواف الرسم البياني ، والرؤوس الأولية والنهائية ، على التوالي (1 & lt ؛ = n & lt ؛ = 100000 ؛ 0 & lt ؛ = م & lt ؛ = 200000 ؛ 1 & lt ؛ = s ، t & lt ؛ = n).
تحتوي سطور m التالية على أوصاف للحواف ، بمعدل واحد لكل سطر. & nbsp ؛
رقم الحافة الأول موصوف بثلاثة أعداد صحيحة b i و e i و w i - بداية الحافة ونهايتها وطولها ، على التوالي ( 1 & lt؛ = b i ، e i & lt؛ = n؛ | w i | & lt؛ = 1000). & nbsp؛
الرسم البياني لا يحتوي على دورات وحلقات.

الإخراج:
يجب أن يحتوي السطر الأول من ملف الإخراج على عدد صحيح واحد - طول أقصر مسار من s إلى t. & nbsp؛
إذا لم يكن هناك مسار من s إلى t ، فقم بطباعة "لا يمكن الوصول إليه".

أمثلة:
نبسب ؛ <الجسم>
إدخال الإخراج
2 1 1 2
1 2-10 		-10
2 1 2 1
1 2-10 		لا يمكن الوصول

time 1500 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!