Problem
एक प्रोग्राम लिखें जो एक दिए गए शीर्ष से प्रत्येक दूसरे शीर्ष तक गैर-ऋणात्मक किनारे की लंबाई के साथ एक अप्रत्यक्ष भारित ग्राफ में दूरी का पता लगाएगा। बड़े विरल ग्राफ़ के लिए प्रोग्राम तेज़ होना चाहिए।
इनपुट
इनपुट की पहली पंक्ति में संख्या NUM — दिज्क्स्ट्रा के एल्गोरिथ्म के विभिन्न रनों की संख्या (विभिन्न ग्राफ़ पर)। इसके बाद NUM ब्लॉक होते हैं, जिनमें से प्रत्येक की संरचना निम्न है।
ब्लॉक की पहली पंक्ति में दो संख्याएँ हैं N और M एक रिक्ति द्वारा अलग की गई हैं — शीर्षों की संख्या और ग्राफ के किनारों की संख्या। इसके बाद M रेखाएं आती हैं, जिनमें से प्रत्येक में रिक्त स्थान द्वारा अलग किए गए तीन पूर्णांक होते हैं। उनमें से पहले दो, 0 से N–प्रत्येक के बीच, संबंधित किनारे के सिरों को दर्शाते हैं, तीसरा — 0 से 20000 तक और इस किनारे की लंबाई को दर्शाता है। आगे, ब्लॉक की अंतिम पंक्ति में, 0 से N–1 — शिखर, वह दूरी जिससे आपको खोज करने की आवश्यकता है।
एक परीक्षण NUM में विभिन्न ग्राफ़ की संख्या 5 से अधिक नहीं है। शीर्षों की संख्या 60000 से अधिक नहीं है, किनारे — 200000.
छाप
मानक आउटपुट (स्क्रीन) NUM पंक्तियों पर प्रिंट करें, प्रत्येक में भारित अप्रत्यक्ष ग्राफ के निर्दिष्ट शुरुआती शीर्ष से उसके 0वें, पहले, दूसरे आदि तक की दूरी। कोने (अंतिम संख्या के बाद एक अतिरिक्त स्थान की अनुमति है)। यदि निर्दिष्ट प्रारंभिक एक से कुछ शीर्ष तक नहीं पहुंचा जा सकता है, तो दूरी के बजाय संख्या 2009000999 प्रिंट करें (यह गारंटी है कि सभी वास्तविक दूरियां कम हैं)।
उदाहरण
<टेबल क्लास = "टेबल टेबल-कंडेंस्ड टेबल-होवर">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
1
5 7
1 2 5
1 3 2
2 3 4
2 4 3
3 4 6
0 3 20
0 4 10
1 |
18 0 5 2 8 |