1-के बीएफएस
Problem
आपको एक निर्देशित भारित ग्राफ दिया जाता है। एल्गोरिथम 1 - k BFS का उपयोग करके आपको शीर्ष 1 से अन्य सभी की दूरी ज्ञात करनी होगी।
इनपुट
पहली पंक्ति में 2 पूर्णांक n और m होते हैं, क्रमशः ग्राफ़ में शीर्षों और किनारों की संख्या। निम्नलिखित m पंक्तियों में 3 नंबर हैं प्रत्येक a और b - वे शीर्ष जो किनारे को जोड़ते हैं और c - इस किनारे का वजन (a, b, c >= 0).
आउटपुट
n-1 संख्या को एक स्थान से अलग करना आवश्यक है - शीर्ष 1 से अन्य सभी की दूरी, यदि 1 से कोई संभावित पथ नहीं है से i वर्टेक्स, तो आपको Impossible को आउटपुट करना होगा।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
<टीडी>
<पूर्व>
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
<टीडी>
<पूर्व>
1 4 3 6 4 असंभव असंभव असंभव