यहाँ रूसी से हिंदी में अनुवादित प्रोग्रामिंग कार्य का टेक्स्ट दिया गया है: कक्षाओं का उपयोग करके ग्राफ में सबसे छोटा रास्ता खोजना

PHP Hard classes

कार्य «यहाँ रूसी से हिंदी में अनुवादित प्रोग्रामिंग कार्य का टेक्स्ट दिया गया है: कक्षाओं का उपयोग करके ग्राफ में सबसे छोटा रास्ता खोजना»

ग्राफ वर्ग को लागू करें जो एक भारित निर्देशित ग्राफ का प्रतिनिधित्व करता है। क्लास में किनारा जोड़ने के लिए addEdge(int $from, int $to, int $weight) विधि और डायज्कस्ट्रा एल्गोरिदम का उपयोग करके शीर्ष $start से $end तक सबसे छोटा रास्ता खोजने के लिए shortestPath(int $start, int $end) विधि शामिल होनी चाहिए। यदि कोई रास्ता मौजूद नहीं है, तो विधि को -1 लौटाना चाहिए। यह गारंटी है कि किनारों के भार सकारात्मक हैं, शीर्षों की संख्या 1000 से अधिक नहीं है, और किनारों की संख्या 10000 तक है।

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

पहली पंक्ति में रिक्त स्थान द्वारा N (शीर्षों की संख्या) और M (किनारों की संख्या) दिए गए हैं। इसके बाद M पंक्तियों में किनारे दिए गए हैं: from to weight। अंतिम पंक्ति में start और end दिए गए हैं।

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

पूर्णांक — start से end तक के पथ की न्यूनतम लागत, या -1 यदि कोई पथ नहीं है।

उदाहरण

उदाहरण 1

इनपुट

10

आउटपुट

87

उदाहरण 2

इनपुट

आउटपुट

15

उदाहरण 3

इनपुट

1

आउटपुट

0

उदाहरण 4

इनपुट

1
2 7
1

आउटपुट

-1

main.php