AR
RU
EN
ES
ZH
FR
DE
PT
HI
<div class="task-content"> <p>ابحث عن أقصر مسار في الرسم البياني باستخدام الفئات</p> </div>
PHP
Hard
classes
مهمة «<div class="task-content"> <p>ابحث عن أقصر مسار في الرسم البياني باستخدام الفئات</p> </div>»
قم بتنفيذ الفئة Graph لتمثيل رسم بياني موجه موزون. يجب أن تحتوي الفئة على طرق addEdge(int $from, int $to, int $weight) لإضافة حافة و shortestPath(int $start, int $end) لإيجاد أقصر مسار من العقدة $start إلى $end باستخدام خوارزمية ديكسترا. إذا لم يكن هناك مسار، يجب أن تعيد الطريقة -1. من المضمون أن أوزان الحواف موجبة، وأن عدد العقد لا يتجاوز 1000، وعدد الحواف يصل إلى 10000.
تنسيق الإدخال
في السطر الأول، يتم إعطاء N (عدد الرؤوس) و M (عدد الحواف) مفصولين بمسافة. بعد ذلك، في M من الأسطر، يتم إعطاء الحواف: from to weight. في السطر الأخير، يتم إعطاء start و end.
تنسيق الإخراج
<p>عدد صحيح — أقل تكلفة للمسار من <code>start</code> إلى <code>end</code>، أو <code>-1</code> إذا لم يكن هناك مسار.</p>
أمثلة
مثال 1
الإدخال
10
الإخراج
87
مثال 2
الإدخال
3 2
1 2 5
2 3 10
1 3
الإخراج
15
مثال 3
الإدخال
1
الإخراج
0
مثال 4
الإدخال
2 1
1 2 7
2 1
الإخراج
-1
main.php