Module: फ्लोयड का एल्गोरिदम

आपको एक निर्देशित भारित ग्राफ दिया जाता है। इसके आसन्न मैट्रिक्स का उपयोग करते हुए, आपको प्रत्येक जोड़ी के शीर्ष के लिए यह निर्धारित करने की आवश्यकता है कि उनके बीच सबसे छोटा रास्ता है या नहीं।

 

टिप्पणी: सबसे छोटा रास्ता दो कारणों से मौजूद नहीं हो सकता है:

इनपुट फ़ाइल की पहली पंक्ति में एक ही संख्या है: N (1 <=N <=100) — ग्राफ के शीर्षों की संख्या अगली N पंक्तियों में प्रत्येक में N संख्याएँ हैं — ग्राफ़ का सन्निकट मैट्रिक्स (i-वें पंक्ति में j-वें नंबर वर्टेक्स i से वर्टेक्स j तक किनारे के वजन से मेल खाता है): संख्या 0 का अर्थ कोई किनारा नहीं है, और कोई अन्य संख्या — इसी वजन के किनारे की उपस्थिति। सभी सापेक्ष संख्याएं 100 से अधिक नहीं होती हैं।

 

N संख्याओं की N पंक्तियाँ प्रिंट करें। i-वें पंक्ति में j-वें नंबर को शीर्ष i से शीर्ष j तक के सबसे छोटे पथ के अनुरूप होना चाहिए। अगर कोई रास्ता नहीं है तो नंबर 0 होना चाहिए, अगर कोई सबसे छोटा रास्ता है तो 1 और अगर रास्ते हैं लेकिन मनमाने ढंग से छोटे वजन के रास्ते हैं तो 2 होना चाहिए।

उदाहरण <टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 1 <टीडी> <टीडी>