<div> <p>ابحث عن أقصر مسار في رسم بياني بأوزان قابلة للتغيير</p> </div>

Go Hard maps

مهمة «<div> <p>ابحث عن أقصر مسار في رسم بياني بأوزان قابلة للتغيير</p> </div>»

<div>بيانات رسم بياني غير موجه وموزون مكون من N رأس و M حافة. يمكن أن تتغير أوزان الحواف بمرور الوقت: لكل حافة، يتم تحديد وزن أولي ومصفوفة من التغييرات (لحظة زمنية وقيمة جديدة). مطلوب إيجاد أقصر مسار من الرأس 1 إلى الرأس N في اللحظة الزمنية T. يمكن أن يمر المسار عبر أي رؤوس، ولكن يتم أخذ أوزان الحواف في اللحظة الزمنية T. إذا لم يكن هناك مسار، قم بإخراج -1.</div>

تنسيق الإدخال

السطر الأول: N M T (1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, 0 ≤ T ≤ 10^9). بعد ذلك M سطر: u v w0 k (1 ≤ u,v ≤ N, 1 ≤ w0 ≤ 1000, 0 ≤ k ≤ 100) — حافة، وزن ابتدائي، عدد التغييرات. ثم k سطر: ti wi (0 ≤ ti ≤ T, 1 ≤ wi ≤ 1000) — لحظة زمنية ووزن جديد. التغييرات مرتبة حسب ti.

تنسيق الإخراج

عدد صحيح واحد — الحد الأدنى لمجموع أوزان الحواف في المسار من 1 إلى N في اللحظة T، أو -1.

أمثلة

مثال 1

الإدخال

1 0
2 10 1
5

الإخراج

5

main.go