خوارزمية Dijkstra في O (M logN)
Problem
اكتب برنامجًا يعثر على المسافات في رسم بياني مرجح غير موجه بأطوال حواف غير سالبة ، من رأس معين إلى كل رأس آخر. يجب أن يكون البرنامج سريعًا بالنسبة إلى الرسوم البيانية المتفرقة الكبيرة.
إدخال
يحتوي السطر الأول من الإدخال على الرقم NUM & mdash؛ عدد مرات التشغيل المختلفة لخوارزمية Dijkstra (على رسوم بيانية مختلفة). ويتبع ذلك NUM من الكتل ، لكل منها البنية التالية.
يحتوي السطر الأول من الكتلة على رقمين & nbsp؛ N & nbsp؛ & nbsp؛ M مفصولة بمسافة & mdash؛ عدد الرؤوس وعدد حواف الرسم البياني. ويتبع ذلك & nbsp؛ M & nbsp؛ خطوط ، كل منها يحتوي على ثلاثة أعداد صحيحة مفصولة بمسافات. أول اثنين منهم ، تتراوح من 0 إلى & nbsp؛ N & ndash؛ 1 لكل منهما ، تشير إلى نهايات الحافة المقابلة ، والثالث & mdash؛ يتراوح من 0 إلى 20000 ويشير إلى طول هذه الحافة. علاوة على ذلك ، في السطر الأخير من الكتلة ، رقم واحد من 0 إلى & nbsp؛ N & ndash؛ 1 & mdash؛ ذروة ، المسافة التي تريد البحث منها.
لا يتجاوز عدد الرسوم البيانية المختلفة في اختبار واحد NUM & nbsp؛ 5. عدد الرؤوس لا يتجاوز 60000 ، والحواف و [مدش] ؛ 200000.
بيانات النشر
طباعة لمخرجات قياسية (شاشة) NUM سطور ، كل منها يحتوي على & nbsp؛ N i & nbsp؛ أرقام مفصولة بمسافات & mdash؛ المسافة من قمة البداية المحددة للرسم البياني الموزون غير الموجه إلى الصفر ، الأول ، الثاني ، إلخ. الرؤوس (يُسمح بمسافة إضافية بعد الرقم الأخير). إذا كان بعض الرؤوس لا يمكن الوصول إليه من الرأس الأولي المحدد ، فقم بطباعة الرقم 2009000999 بدلاً من المسافة (نضمن أن تكون جميع المسافات الحقيقية أقل).
أمثلة
| # |
إدخال |
الإخراج |
<الجسم>
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 & nbsp؛ |