Кратчайшая дорога


Отправить решение Решать в редакторе

Сложность: 40%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Тип задачи
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В стране N городов, пронумерованных от 1 до N, и M двусторонних дорог. Каждая дорога соединяет два города и имеет длину. Между двумя городами может быть несколько дорог.

Найдите длину кратчайшего пути из города 1 в город N.

Входные данные

В первой строке — два целых числа N и M (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000). Далее M строк, в каждой — три целых числа u, v, w: дорога между городами u и v (u ≠ v) длиной w (1 ≤ w ≤ 1 000 000 000).

Выходные данные

Одно целое число — длина кратчайшего пути из города 1 в город N. Если добраться невозможно, выведите -1.

Пример 1

Вход:

5 6
1 2 4
1 3 1
3 2 2
2 4 5
3 4 8
4 5 3

Выход:

11

Пример 2

Вход:

4 2
1 2 7
3 4 2

Выход:

-1

Пояснение

В первом примере кратчайший путь 1 → 3 → 2 → 4 → 5 имеет длину 1 + 2 + 5 + 3 = 11. Во втором примере города 1 и 4 не связаны. Длина пути может не поместиться в 32-битный тип. Используйте алгоритм Дейкстры с кучей (очередью с приоритетом).


Комментарии

Еще нет ни одного комментария.