<div> <p>ग्राफ में परिवर्तनीय भार के साथ न्यूनतम पथ खोजना</p> </div>

Go Hard maps

कार्य «<div> <p>ग्राफ में परिवर्तनीय भार के साथ न्यूनतम पथ खोजना</p> </div>»

दिया गया एक अदिश भारित ग्राफ है जिसमें N शीर्ष और M किनारे हैं। किनारों के भार समय के साथ बदल सकते हैं: प्रत्येक किनारे के लिए एक प्रारंभिक भार और परिवर्तनों की एक सूची (समय बिंदु और नया मान) दी गई है। समय T पर शीर्ष 1 से शीर्ष N तक का न्यूनतम पथ ज्ञात करना आवश्यक है। पथ किसी भी शीर्ष से होकर जा सकता है, लेकिन किनारों के भार समय T पर लिए जाते हैं। यदि कोई पथ मौजूद नहीं है, तो -1 आउटपुट करें।

इनपुट प्रारूप

पहली पंक्ति: 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 के अनुसार क्रमबद्ध हैं।

आउटपुट प्रारूप

एक पूर्णांक — T समय पर 1 से N तक के पथ में किनारों के भारों का न्यूनतम योग, या -1।

उदाहरण

उदाहरण 1

इनपुट

1 0
2 10 1
5

आउटपुट

5

main.go