फोर्ड बेलमैन
Problem
एक निर्देशित ग्राफ दिया गया है जिसमें कई किनारे और लूप हो सकते हैं। प्रत्येक किनारे का वजन एक पूर्णांक (संभवतः नकारात्मक) के रूप में व्यक्त किया जाता है। यह गारंटी है कि कोई नकारात्मक भार चक्र नहीं है।
आपको शीर्ष संख्या 1 से अन्य सभी शीर्षों तक के सबसे छोटे रास्तों की लंबाई की गणना करने की आवश्यकता है।
इनपुट
प्रोग्राम पहले नंबर N (1 <= N <= 100) – ग्राफ़ शीर्षों की संख्या और संख्या M (0 <= M <= 10000) – पसलियों की संख्या। निम्नलिखित पंक्तियों में किनारों का वर्णन करने वाली संख्याओं के एम ट्रिपल हैं: किनारे की शुरुआत, किनारे का अंत, और वजन (वजन -100 से 100 तक एक पूर्णांक है)।
आउटपुट
प्रोग्राम को N संख्याएँ प्रदर्शित करनी चाहिए – ग्राफ के शीर्ष संख्या 1 से सभी शीर्षों की दूरी। यदि संबंधित शीर्ष के लिए कोई पथ नहीं है, तो पथ की लंबाई के बजाय संख्या 30000 प्रिंट करें।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
0 10 20 30000 30000 30000 |