सबसे छोटा मार्ग खोजें 1
आपको एक मानचित्र दिया गया है, जिसमें
n शहर हैं और उन्हें जोड़ने वाली m द्विदिश सड़कें हैं। प्रत्येक सड़क की लंबाई एक गैर-ऋणात्मक पूर्णांक होती है, जिसे के रूप में दर्शाया गया है। आपका कार्य शहर 1 से शहर n के बीच जाने वाले सबसे छोटे मार्ग की लंबाई निकालना है।इनपुट
पहली पंक्ति में दो स्पेस से विभाजित पूर्णांक
n और m () होते हैं, जो क्रमशः शहरों की संख्या और सड़कों की संख्या को दर्शाते हैं।अगली
m पंक्तियों में से प्रत्येक पंक्ति में तीन स्पेस से विभाजित पूर्णांक , , और होते हैं। ये शहर और शहर के बीच एक सड़क को दर्शाते हैं, जिसकी लंबाई होती है ()।आउटपुट
आपके प्रोग्राम को शहर
1 से शहर n तक जाने वाले सबसे छोटे मार्ग की लंबाई को प्रिंट करना चाहिए।उदाहरण
इनपुट | आउटपुट |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 6 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 1 MB