لنلقِ نظرة على مثال إيجاد أقصر طريق. يتم توفير شبكة من الطرق السريعة التي تربط مناطق المدينة. بعض الطرق هي اتجاه واحد. ابحث عن أقصر الطرق من وسط المدينة إلى كل مدينة في المنطقة.
لحل هذه المشكلة يمكنك استخدام خوارزمية ديكستراهي خوارزمية رسم بياني اخترعها العالم الهولندي إي. ديكسترا في عام 1959. إيجاد أقصر مسافة من أحد رؤوس الرسم البياني إلى جميع الرؤوس الأخرى. يعمل فقط مع الرسوم البيانية التي لا تحتوي على حواف ذات وزن سالب.
لنفترض أنك بحاجة إلى العثور على أقصر المسافات من القمة الأولى إلى جميع النقاط الأخرى.
تشير الدوائر إلى القمم، والخطوط تشير إلى المسارات بينها (حواف الرسم البياني). يشار إلى أرقام القمم في الدوائر، ويشار إلى وزنها فوق الحواف - طول المسار. بجانب كل قمة توجد علامة حمراء - طول أقصر مسار إلى هذه القمة من القمة 1.
يتم تعيين تسمية الرأس 1 نفسها على 0، ويتم تعيين تسميات القمم الأخرى على عدد كبير لا يمكن الوصول إليه (من الناحية المثالية، اللانهاية). وهذا يعكس أن المسافات من القمة 1 إلى القمم الأخرى ليست معروفة بعد. يتم وضع علامة على جميع قمم الرسم البياني على أنها غير تمت زيارتها. 
الخطوة الأولى
الرأس 1 لديه الحد الأدنى من التسمية لجيرانه هم الرؤوس 2 و3 و6. نلتف حول جيران الرأس بالتناوب.
الجار الأول للقمة 1 هو القمة 2، لأن طول المسار إليها ضئيل. طول المسار إليها عبر الرأس 1 يساوي مجموع أقصر مسافة إلى الرأس 1، وقيمة تسميتها، وطول الحافة الممتدة من الأول إلى الثاني، أي 0 + 7 = 7. وهذا أقل من التسمية الحالية للقمة 2 (10000)، وبالتالي فإن التسمية الجديدة للقمة الثانية هي 7. 
وبالمثل، نجد أطوال المسار لجميع الجيران الآخرين (الرؤوس 3 و 6).
يتم فحص كافة جيران قمة الرأس 1. تعتبر المسافة الدنيا الحالية إلى الذروة 1 نهائية ولا يمكن مراجعتها. تم وضع علامة على Vertex 1 على أنها تمت زيارتها.
الخطوة الثانية
يتم تكرار الخطوة 1 من الخوارزمية. مرة أخرى نجد "الأقرب" من القمم غير المزارة. هذه هي القمة 2 مع التسمية 7.
مرة أخرى، نحاول تقليل تسميات جيران القمة المحددة، في محاولة لتمرير القمة الثانية إليهم. جيران الرأس 2 هم الرؤوس 1 و 3 و 4.
تمت زيارة Vertex 1 بالفعل. الجار التالي للقمة 2 هو الرأس 3، لأنه يحتوي على الحد الأدنى من علامة القمم التي تم وضع علامة "لم تتم زيارتها". إذا ذهبت إليه من خلال 2، فسيكون طول هذا المسار يساوي 17 (7 + 10 = 17). لكن التسمية الحالية للرأس الثالث هي 9، و9< 17, поэтому метка не меняется.
جار آخر للقمة 2 هو القمة 4. إذا ذهبت إليها خلال الثانية، فسيكون طول هذا المسار يساوي 22 (7 + 15 = 22). منذ 22<10000, устанавливаем метку вершины 4 равной 22.
تم عرض جميع جيران vertex 2، قم بوضع علامة عليها كمواقع تمت زيارتها.
خطوة ثالثة
نكرر خطوة الخوارزمية باختيار الرأس 3. وبعد "معالجته" نحصل على النتائج التالية. 
الخطوة الرابعة
الخطوة الخامسة
الخطوة السادسة
وبالتالي، فإن أقصر مسار من الرأس 1 إلى الرأس 5 هو المسار عبر القمم 1 — 3 — 6 — 5
، لأننا بهذه الطريقة نكتسب وزنًا لا يقل عن 20.
لنبدأ في اشتقاق أقصر طريق. نحن نعرف طول المسار لكل قمة، والآن سننظر إلى القمم من النهاية. نحن نعتبر الرأس النهائي (في هذه الحالة، الرأس 5
)، وبالنسبة لجميع القمم التي يتصل بها، نجد طول المسار عن طريق طرح وزن الحافة المقابلة من طول مسار الرأس النهائي.
نعم القمة 5
لديه طول المسار 20
. إنه متصل بالقمم 6
و 4
.
للأعلى 6
نحصل على الوزن 20 - 9 = 11 (متطابق).
للأعلى 4
نحصل على الوزن 20 - 6 = 14 (غير متطابق).
إذا حصلنا نتيجة لذلك على قيمة تتطابق مع طول مسار الرأس المعني (في هذه الحالة، الرأس 6
)، ومن ثم تم الانتقال إلى القمة النهائية. نحتفل بهذه الذروة على المسار المطلوب.
بعد ذلك، نحدد الحافة التي وصلنا من خلالها إلى قمة الرأس 6
. وهكذا حتى نصل إلى البداية.
إذا كان لدينا، نتيجة لمثل هذا الاجتياز، في مرحلة ما نفس القيم لعدة قمم، فيمكننا أن نأخذ أيًا منها - سيكون للعديد من المسارات نفس الطول.
تنفيذ خوارزمية ديكسترا
يتم استخدام مصفوفة مربعة لتخزين أوزان الرسم البياني. تحتوي رؤوس الصفوف والأعمدة على رؤوس الرسم البياني. ويتم وضع أوزان أقواس الرسم البياني في الخلايا الداخلية للجدول. لا يحتوي الرسم البياني على حلقات، لذا فإن القطر الرئيسي للمصفوفة يحتوي على قيم صفرية.
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 0 | 7 | 9 | 0 | 0 | 14 |
| 2 | 7 | 0 | 10 | 15 | 0 | 0 |
| 3 | 9 | 10 | 0 | 11 | 0 | 2 |
| 4 | 0 | 15 | 11 | 0 | 6 | 0 |
| 5 | 0 | 0 | 0 | 6 | 0 | 9 |
| 6 | 14 | 0 | 2 | 0 | 9 | 0 |
التنفيذ في C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#define _CRT_SECURE_NO_WARNINGS
#يشمل
#يشمل
#تعريف الحجم 6
انت مين()
{
كثافة العمليات أ؛ // مصفوفة الاتصال
كثافة العمليات د؛ // الحد الأدنى للمسافة
في التلفاز؛ // تمت زيارة القمم
درجة الحرارة المؤقتة، مؤشر صغير، دقيقة؛
int begin_index = 0;
نظام("chcp 1251");
نظام("cls");
// تهيئة مصفوفة الاتصال
ل(int i = 0; i
أ[i][i] = 0;
ل(int j = i + 1; j
scanf("%d" , &temp);
a[i][j] = temp;
a[j][i] = temp;
}
}
// إخراج مصفوفة الاتصال
ل(int i = 0; i
ل(int j = 0; j
printf("\n");
}
// تهيئة القمم والمسافات
ل(int i = 0; i
د[i] = 10000;
v[i] = 1;
}
د = 0؛
// خطوة الخوارزمية
يفعل(
مؤشر صغير = 10000؛
الحد الأدنى = 10000؛
ل(int i = 0; i
إذا ((v[i] == 1) && (d[i]
دقيقة = د[i];
مؤشر صغير = i;
}
}
// أضف الحد الأدنى للوزن الموجود
// إلى الوزن الحالي للقمة
// ومقارنتها بالوزن الأدنى الحالي للقمة
إذا (المؤشر الأدنى! = 10000)
{
ل(int i = 0; i
إذا (أ[i] > 0)
{
درجة الحرارة = دقيقة + أ[i]؛
إذا (درجة الحرارة< d[i])
{
d[i] = temp;
}
}
}
الخامس = 0؛
}
) بينما (minindex< 10000);
// اطبع أقصر المسافات إلى القمم
برينتف ( "\nأقصر المسافات إلى القمم:\n");
ل(int i = 0; i
// استعادة المسار
النسخة الدولية؛ // مجموعة من القمم التي تمت زيارتها
نهاية كثافة العمليات = 4؛ // مؤشر قمة النهاية = 5 - 1
النسخة = نهاية + 1؛ // عنصر البداية - قمة النهاية
كثافة العمليات ك = 1؛ // فهرس الرأس السابق
الوزن الصحيح = د؛ // وزن الرأس النهائي
بينما (النهاية! = begin_index) // حتى نصل إلى القمة الأولية
{
ل(int i = 0; i
إذا (أ[i] != 0) // إذا كان هناك اتصال
{
int temp = الوزن - a[i]; // تحديد وزن المسار من الرأس السابق
إذا (درجة الحرارة == د[i]) // إذا كان الوزن مطابقًا للوزن المحسوب
{ // هذا يعني أنه كان هناك انتقال من هذه القمة
الوزن = درجة الحرارة؛ // احفظ الوزن الجديد
النهاية = أنا؛ // احفظ الرأس السابق
ver[k] = i + 1; // واكتبها في مصفوفة
ك++;
}
}
}
// إخراج المسار (ينتهي قمة البداية في نهاية مصفوفة العناصر k)
برينتف ( "\nإخراج المسار الأقصر\n");
لـ (int i = k - 1; i >= 0; i--)
printf("%3d " , ver[i]);
getchar(); getchar();
العودة 0؛
}
نتيجة التنفيذ
خلف: أقصر الطرقاليوم هي مهمة حيوية وتستخدم في كل مكان تقريبا، من العثور على الطريق الأمثل بين جسمين على الأرض (على سبيل المثال، أقصر طريق من المنزل إلى الجامعة)، في أنظمة الطيار الآلي، إلى إيجاد الطريق الأمثل أثناء النقل، وتبديل حزم المعلومات في الشبكات وغيرها
يتم اعتبار أقصر مسار باستخدام كائن رياضي يسمى الرسم البياني. يبحث أقصر الطرقيتم إجراؤه بين رأسين محددين في الرسم البياني. والنتيجة هي مسار، أي سلسلة من القمم والحواف التي تقع على رأسين متجاورين، وطولها.
دعونا ننظر إلى ثلاثة من أكثر خوارزمية فعالةالعثور على أقصر الطرق:
- خوارزمية ديكسترا;
- خوارزمية فلويد؛
- خوارزميات البحث.
يتم تنفيذ هذه الخوارزميات بسهولة مع عدد صغير من القمم في الرسم البياني. مع زيادة عددهم، مشكلة البحث أقصر الطرقيصبح أكثر تعقيدا.
خوارزمية ديكسترا
هذه الخوارزمية هي خوارزمية رسم بياني، اخترعها العالم الهولندي إي. ديكسترا في عام 1959. تعثر الخوارزمية على أقصر مسافة من أحد رؤوس الرسم البياني إلى جميع الرؤوس الأخرى وتعمل فقط مع الرسوم البيانية التي لا تحتوي على حواف ذات وزن سالب.
يتم تعيين وزن لكل قمة - وهذا هو وزن المسار من القمة الأولية إلى هذه القمة. أيضا، يمكن تحديد كل قمة. إذا تم تحديد قمة، فإن المسار منها إلى القمة الأولية هو الأقصر، وإذا لم يكن الأمر كذلك، فهو مؤقت. من خلال اجتياز الرسم البياني، تحسب الخوارزمية المسار لكل قمة، وإذا تبين أنها الأقصر، فإنها تحدد القمة. يصبح وزن هذه القمة هو وزن المسار. بالنسبة لجميع الجيران لقمة معينة، تحسب الخوارزمية أيضًا الوزن، ولكن لا تختارهم تحت أي ظرف من الظروف. تنتهي الخوارزمية من عملها بعد أن وصلت إلى القمة النهائية والوزن أقصر الطرقيصبح وزن الرأس النهائي.
خوارزمية ديكسترا
الخطوة 1. يتم تعيين وزن يساوي اللانهاية لجميع القمم، باستثناء الرأس الأول، ويتم تعيين وزن يساوي 0 للرأس الأول.
الخطوة 2. لم يتم تحديد كافة القمم.
الخطوة 3. تم إعلان القمة الأولى الحالية.
الخطوة 4. يتم إعادة حساب وزن جميع القمم غير المحددة باستخدام الصيغة: وزن الرأس غير المحدد هو الحد الأدنى لعدد الوزن القديم لهذا الرأس، ومجموع وزن الرأس الحالي ووزن الحافة التي تربط الرأس. الرأس الحالي إلى الرأس غير المحدد.
الخطوة 5. من بين القمم غير المحددة، يتم البحث عن القمم ذات الوزن الأدنى. إذا لم يتم العثور على واحد، أي أن وزن جميع القمم يساوي ما لا نهاية، فإن المسار غير موجود. وبالتالي فإن الناتج هو . وإلا فإن الرأس الذي تم العثور عليه يصبح هو الرأس الحالي. انها تبرز.
الخطوة 6. إذا كان الرأس الحالي هو الرأس النهائي، فسيتم العثور على المسار، ووزنه هو وزن الرأس النهائي.
الخطوة 7. انتقل إلى الخطوة 4.
في تنفيذ البرمجيات خوارزمية ديكسترالنقم بإنشاء مجموعة S من القمم التي تعرف بالفعل أقصر المسارات من الرأس الأولي. في كل خطوة، تتم إضافة أحد القمم المتبقية إلى المجموعة S، وتكون المسافة من الرأس الأولي أقل من القمم الأخرى المتبقية. في هذه الحالة، سوف نستخدم المصفوفة D، التي تكتب فيها الأطوال أقصر الطرقلكل قمة. عندما تحتوي المجموعة S على جميع رؤوس الرسم البياني، فإن المصفوفة D ستحتوي على الأطوال أقصر الطرقمن قمة البداية إلى كل قمة.
بالإضافة إلى المصفوفات المشار إليها، سوف نستخدم مصفوفة ذات أطوال C، حيث العنصر C هو طول الحافة (i,j)، إذا لم يكن هناك حافة، فيفترض أن طوله يساوي اللانهاية، أي ، أكبر من أي طول فعلي للحواف. في الواقع، المصفوفة C هي مصفوفة الجوار، حيث يتم استبدال جميع العناصر الصفرية بما لا نهاية.
لتحديد ال
خوارزمية ديكسترا هي خوارزمية رسم بياني تجد أقصر مسار بين رأسين محددين في رسم بياني بأطوال قوس غير سالبة. غالبًا ما يتم أيضًا طرح مهمة حساب أقصر مسار من قمة معينة إلى جميع القمم الأخرى. تُستخدم الخوارزمية على نطاق واسع في البرمجة، على سبيل المثال، يتم استخدامها في بروتوكولات التوجيه.
وصف
مدخلات الخوارزمية عبارة عن رسم بياني موجه مرجح بأقواس ذات وزن غير سالب. الناتج عبارة عن مجموعة من أقصر المسارات من قمة معينة إلى قمة أخرى.
في البداية، من المفترض أن تكون المسافة إلى القمة الأولية صفرًا، والمسافات إلى جميع النقاط الأخرى يفترض أنها لا نهائية. يتم تعبئة مجموعة من الأعلام التي تشير إلى ما إذا تم تمرير الرأس بالأصفار. ثم، في كل خطوة من الدورة، يتم البحث عن قمة ذات مسافة لا تقل عن النقطة الأصلية وعلم يساوي الصفر. يتم وضع علامة عليه ويتم فحص جميع القمم المجاورة. إذا كانت المسافة المحسوبة مسبقًا من الرأس الأصلي إلى الرأس الذي يتم فحصه أكبر من مجموع المسافة إلى الرأس الحالي وطول الحافة منه إلى الرأس الذي يتم فحصه، فإن المسافة إلى الرأس الذي يتم فحصه تكون مساوية إلى المسافة إلى الحافة الحالية + من التيار إلى الحافة التي يتم فحصها. تنتهي الدورة عندما تصبح أعلام جميع القمم تساوي 1، أو عندما تكون المسافة إلى جميع القمم ذات العلم 0 لا نهائية. الحالة الأخيرة ممكنة فقط إذا تم فصل الرسم البياني.
خوارزمية ديكسترا في الكود الزائف
مدخل: مع: مجموعة من المصفوفة الحقيقية لأطوال قوس الرسم البياني؛ s هو الرأس الذي يتم البحث منه عن أقصر طريق و t هو الرأس الذي يتم البحث عنه.
الإخراج: المتجهات T: مجموعة حقيقية؛ و N: مجموعة من 0..r. إذا كان الأعلى الخامستقع على أقصر طريق من سل ر،الذي - التي تلفزيون]- طول أقصر طريق من سل ذ؛ حسنًا] -الذروة التي سبقتها مباشرة فيعلى أقصر طريق.
Н – مصفوفة تتوافق فيها قمة n مع قمة m، السابقة في الطريق إلى n من s.
T عبارة عن مصفوفة تتوافق فيها قمة الرأس n مع المسافة منه إلى s.
X عبارة عن مصفوفة تتوافق فيها قمة الرأس n مع 1 إذا كان المسار إليها معروفًا، و0 إذا لم يكن معروفًا.
تهيئة المصفوفة:
ل الخامسمن 1 إلى ريفعل
ت[الخامس]: = ∞ (أقصر طريق غير معروف)
X[v]: = 0 (جميع القمم غير محددة)
ح[ق]: = 0 ( س لا شيء يسبق)
تي [ق]: = 0 (أقصر مسار له طول 0...)
X[ق]: = 1 (... وهو مشهور) الخامس : = س (الأعلى الحالي)
م: (ملاحظات التحديث)
ل و∈ز( و) يفعل
لو العاشر[i] = 0 & تي [أنا]> تلفزيون] + جثم
تي [أنا]: = تلفزيون] + ج(تم العثور على طريق أقصر من س الخامس وخلال الخامس }
ح [ش]:= الخامس(تذكر ذلك)
م: = ∞
الخامس : = 0
(إيجاد نهاية أقصر طريق)
ل ومن 1 إلى ص يفعل
لو X[ش] = 0 &T[ش]< رثم
الخامس:= ش;
م:= تي [ش](قمة الخامس ينتهي أقصر طريق من س
لو الخامس = 0 ثم
توقف (لا يوجد طريق من س الخامس ر) إنهاء إذا
لو الخامس= رثم
توقف (تم العثور على أقصر طريق من س الخامس ر) إنهاء إذا
X[v]: = 1 (تم العثور على أقصر مسار من س الخامس الخامس ) اذهب إلى م
الأساس المنطقي
لإثبات صحة خوارزمية Dijkstra، يكفي ملاحظة أنه في كل مرة يتم تنفيذ جسم الحلقة التي تبدأ بالعلامة M، الخامسيتم استخدام قمة يعرف بها أقصر مسار من القمة س.بمعنى آخر، إذا كان X[v] = 1، فإن T[v] = d(s,v) , وجميع القمم على المسار (s,v) المحددة بواسطة المتجه H لها نفس الخاصية، أي
Vu T[u] = 1 => T[u] = d(s,u)&T] = 1.
في الواقع (عن طريق الاستقراء)، أول مرة الخامسيتم استخدام قمة الرأس حيث يكون أقصر مسار فارغًا ويبلغ طوله 0 (لا يمكن أن تكون المسارات غير الفارغة أقصر لأن أطوال الأقواس غير سالبة). دع T[u] = d(s,u) لجميع القمم المحددة سابقا و.النظر في قمة الرأس المسمى حديثا الخامس، والذي يتم تحديده من الشرط T[v] = min T[i]. لاحظ أنه إذا كان المسار الذي يمر عبر القمم المحددة معروفًا، فإن أقصر مسار معروف. لنفترض (بالتناقض) أن T[v]> d(s, v)، أي المسار الموجود المؤدي من سالخامس الخامس،ليس الأقصر. ثم يجب أن تكون هناك قمم غير محددة على هذا المسار. النظر في الرأس الأول ثعلى هذا المسار، بحيث T[w] = 0. لدينا: T[ث] = د(ق،ث)⩽د(ق>ت)< Т[v],что противоречит выбору вершины u.
تعقيد الوقت
يعتمد تعقيد خوارزمية ديكسترا على طريقة العثور على قمة غير مزارة بأقل مسافة من النقطة الأصلية، وطريقة تخزين مجموعة القمم غير المزارة، وطريقة تحديث التسميات. دع n هو عدد القمم، ودع m هو عدد الحواف في الرسم البياني. ثم في أبسط الحالات، عند البحث عن قمة ذات أقل مسافة إلى القمة الأصلية، يتم مسح مجموعة الرؤوس بأكملها، ويتم استخدام مصفوفة لتخزين المسافات، ويكون وقت تشغيل الخوارزمية هو O(n 2) ). يتم تنفيذ الحلقة الرئيسية حوالي n مرات، في كل منها يتم إنفاق حوالي n من العمليات للعثور على الحد الأدنى. تتطلب الدورات عبر جيران كل قمة تمت زيارتها عددًا من العمليات التي تتناسب مع عدد الحواف m (نظرًا لأن كل حافة تحدث مرتين بالضبط في هذه الدورات وتتطلب عددًا ثابتًا من العمليات). وبالتالي، فإن إجمالي وقت تشغيل الخوارزمية هو O(n 2 +m)، ولكن نظرًا لأن m أقل بكثير من n(n-1)، فإن النتيجة النهائية هي O(n 2).
بالنسبة للرسوم البيانية المتفرقة (أي تلك التي تكون فيها m أقل بكثير من n²)، يمكن تخزين القمم غير المزارة في الكومة الثنائية، ويمكن استخدام قيم المسافة كمفتاح. نظرًا لأنه تم تنفيذ الحلقة حوالي n مرة، وعدد مرات الاسترخاء (تغييرات التسمية) لا يزيد عن m، فإن وقت تشغيل هذا التنفيذ هو O(nlogn+mlogn)
مثال
حساب المسافات من الرأس 1 بناءً على القمم القابلة للعبور:
إلى كل مدينة في المنطقة (إذا كان بإمكانك التحرك على الطرق فقط).
الخيار 2.هناك عدد من الرحلات الجوية بين مدن العالم، وتكلفة كل منها معروفة. قد لا تكون تكلفة الرحلة من A إلى B مساوية لتكلفة الرحلة من B إلى A. ابحث عن أقل مسار للتكلفة (ربما مع النقل) من كوبنهاجن إلى بارناول.
تعريف رسمي
مثال
لنفكر في تنفيذ الخوارزمية باستخدام مثال الرسم البياني الموضح في الشكل.
لنفترض أنك بحاجة إلى العثور على أقصر المسافات من القمة الأولى إلى جميع النقاط الأخرى.
التنفيذ في لغات البرمجة
التنفيذ بلغة C (C).
#define SIZE 6 #define INF 1000000000 int a [ SIZE ] [ SIZE ] = (( INF , 5 , INF , INF , INF , INF ),( 1 , 2 , 3 , 4 , 5 , 6 ), // مصفوفة المسار (1، 2، 3، 4، 5، 6)،(1، 2، 3، 4، 5، 6)، // الفهارس الأفقية من النقطة { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // عموديًا إلى نقطة، القيمة - الوزنكثافة العمليات د[حجم]; // مجموعة من أقصر المسارات والمؤشرات ورؤوس الرسم البياني void deikstra () ( int v [ SIZE ]; // مجموعة من التسميات int temp , i ; int minindex , min ; for (i = 0 ; i< SIZE ; i ++ ) { d [ i ] = INF ; // تتم تهيئة مجموعة المسارات إلى ما لا نهاية v[i] = 1; ) د [ 0 ] = 0 ; يفعل( // تنفيذ الخوارزميةمؤشر صغير = INF ; الحد الأدنى = المعلومات النووية؛ من أجل (i = 0؛ i< SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] >0) (درجة الحرارة = دقيقة + أ [minindex] [i]؛ إذا (درجة الحرارة< d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
في نهاية بطولة ليلة رأس السنة الجديدة، قرر الراعي إرسال هدايا بقيمة مليون دولار للفائزين عبر البريد. بمعرفة عدد المشاركين $n$ ووقت تسليم البريد بين بعض فروع Ukrposhta، ابحث عن أقل وقت سيحصل بعده الفائز الأخير على جائزته.
ادخال البيانات
يحتوي السطر الأول على أرقام $3$: عدد المشاركين في البطولة $n$، وعدد جوائز الرعاة $m$، وعدد أوقات التسليم المعروفة بين بعض الفروع $k$. يحتوي السطر التالي على أرقام المشاركين الذين أصبحوا فائزين، مفصولة بمسافة.
بعد ذلك، تأتي أسطر $k$ مكونة من أرقام $3$ تحتوي كل منها على معلومات حول أوقات التسليم المعروفة بين بعض الفروع بالتنسيق: $a$ $b$ $t$، حيث $a$ و $b$ عبارة عن أرقام الأقسام، $t $ $(0 \leqslant t \leqslant 365)$ — وقت تسليم البريد بينهما. يحتوي السطر الأخير على رقم واحد - رقم مكتب البريد الذي سيرسل منه الراعي الجوائز. ومن المعروف أن $1 \leqslant n, m, a, b \leqslant 365$.
انتاج |
إذا تم تسليم جميع الجوائز للمشاركين، فاكتب "الراعي الصالح!" في السطر الأول، وفي السطر التالي الوقت الذي سيحصل بعده الفائز الأخير على جائزته. إذا فشل أحد المشاركين على الأقل في استلام الجائزة، فاطبع عبارة "ليس خطأ الراعي..." في سطر واحد. التعبير عن العبارات بدون علامات الاقتباس.
الاختبارات
| № | ادخال البيانات | انتاج | |
| 1. | 3 2 2 2 3 1 2 3 2 3 4 1 |
الراعي الجيد! 7 |
| 2. | 5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1 |
الراعي الجيد! 16 |
| 3. | 7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7 |
ليس العيب في الراعي... |
| 4. | 5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2 |
الراعي الجيد! 6 |
تحميل...