Контест Senior Задачи на Java обновлено
Кратчайший путь в графе дорог
Условие
Дан неориентированный граф дорог: n городов и m дорог с длинами. Найдите длину кратчайшего пути из города 1 в город n.
Ввод: в первой строке n и m (2 ≤ n ≤ 10⁴, 0 ≤ m ≤ 2·10⁴), далее m строк a b w (1 ≤ a, b ≤ n, 1 ≤ w ≤ 10⁹).
Вывод: длина пути или -1, если пути нет.
Пример
4 5
1 2 1
2 4 5
1 3 2
3 4 1
2 3 1
3
Как подойти
Dijkstra + PriorityQueue с ленивым удалением.
Подсказки: 2
- Веса до 10⁹ и путь до 10⁴ рёбер: какой тип?
- Устаревшие записи в куче нужно пропускать.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.