#25. Eng qisqa yo'l (Dijkstra)
Sizga n ta cho'qqi va m ta yo'nalishsiz qirradan iborat bo'lgan og'irlikli graf beriladi. Har bir qirra ikkita cho'qqini bog'laydi va bosib o'tish uchun o'zining masofasiga (og'irligiga) ega. Barcha qirralarning og'irliklari musbat. Sizning vazifangiz 1-raqamli cho'qqidan boshlab n-raqamli cho'qqigacha yetib borish uchun ketadigan eng qisqa yo'lning umumiy masofasini topishdir.
Birinchi qatorda cho'qqilar soni n va qirralar soni m. Keyingi m ta qatorda uchtadan son: u, v (qirra bog'laydigan cho'qqilar) va w (shu qirraning uzunligi) kiritiladi.
1-cho'qqidan n-cho'qqigacha bo'lgan eng qisqa masofani chiqaring. Agar yo'l mavjud bo'lmasa, -1 chiqaring.
m ≤ 3×10⁵
You are given a weighted graph consisting of n vertices and m undirected edges. Each edge connects two vertices and has its own distance (weight) to traverse. All edge weights are positive. Your task is to find the total distance of the shortest path from vertex 1 to vertex n.
The first line contains the number of vertices n and the number of edges m. The next m lines contain three numbers each: u, v (the vertices connected by the edge) and w (the length of this edge).
Output the shortest distance from vertex 1 to vertex n. If no path exists, output -1.
m ≤ 3×10⁵
Вам дан взвешенный граф, состоящий из n вершин и m неориентированных ребер. Каждое ребро соединяет две вершины и имеет свое расстояние (вес) для прохождения. Все веса ребер положительны. Ваша задача — найти общее расстояние кратчайшего пути от вершины 1 до вершины n.
В первой строке задано количество вершин n и количество ребер m. В следующих m строках задано по три числа: u, v (вершины, соединяемые ребром) и w (длина этого ребра).
Выведите кратчайшее расстояние от вершины 1 до вершины n. Если пути не существует, выведите -1.
m ≤ 3×10⁵
Sizga n ta cho'qqi va m ta yo'nalishsiz qirradan iborat bo'lgan og'irlikli graf beriladi. Har bir qirra ikkita cho'qqini bog'laydi va bosib o'tish uchun o'zining masofasiga (og'irligiga) ega. Barcha qirralarning og'irliklari musbat. Sizning vazifangiz 1-raqamli cho'qqidan boshlab n-raqamli cho'qqigacha yetib borish uchun ketadigan eng qisqa yo'lning umumiy masofasini topishdir.
Kiruvchi ma'lumotlar
Birinchi qatorda cho'qqilar soni n va qirralar soni m. Keyingi m ta qatorda uchtadan son: u, v (qirra bog'laydigan cho'qqilar) va w (shu qirraning uzunligi) kiritiladi.
Chiquvchi ma'lumotlar
1-cho'qqidan n-cho'qqigacha bo'lgan eng qisqa masofani chiqaring. Agar yo'l mavjud bo'lmasa, -1 chiqaring.
Cheklovlar
m ≤ 3×10⁵
Misollar
3 3 1 2 1 2 3 2 1 3 4
3