AR
RU
EN
ES
ZH
FR
DE
PT
HI
إيجاد أطول مسار في رسم بياني باستخدام STL والترتيب الطوبولوجي
C++
Hard
STL
مهمة «إيجاد أطول مسار في رسم بياني باستخدام STL والترتيب الطوبولوجي»
لدينا رسم بياني موجه غير دوري (DAG) يحتوي على N رأس و M حافة. كل حافة لها وزن صحيح (يمكن أن يكون سالبًا). يجب إيجاد طول أطول مسار من رأس بداية معين S إلى جميع الرؤوس الأخرى. إذا كان الرأس غير قابل للوصول، أخرج "INF". استخدم الترتيب الطوبولوجي (خوارزمية كان) والبرمجة الديناميكية. القيود: N ≤ 10^5, M ≤ 2*10^5, الأوزان معامل ≤ 10^9. مضمون أن الرسم البياني لا يحتوي على دورات.
تنسيق الإدخال
السطر الأول: N M S (1 ≤ N ≤ 100000, 0 ≤ M ≤ 200000, 1 ≤ S ≤ N). الأسطر M التالية: u v w (1 ≤ u, v ≤ N, -10^9 ≤ w ≤ 10^9).
تنسيق الإخراج
قم بإخراج N سطر: لكل رأس i (من 1 إلى N)، أخرج طول أطول مسار من S إلى i، أو "INF" إذا كان الرأس غير قابل للوصول. يُعتبر طول المسار من S إلى S مساويًا لـ 0.
أمثلة
مثال 1
الإدخال
4 3 1
1 2 5
1 3 3
2 4 2
الإخراج
0
5
3
7
مثال 2
الإدخال
3 2 1
1 2 -1
2 3 -2
الإخراج
0
-1
-3
main.cpp