Контест Senior Задачи на Kotlin обновлено
Кратчайшие пути: алгоритм Дейкстры
Условие
Дан неориентированный граф с неотрицательными весами рёбер. Найди кратчайшие расстояния от вершины s до всех вершин.
Ввод. n m s (1 ≤ n ≤ 3000, 0 ≤ m ≤ 3000). Далее m строк u v w (1 ≤ u, v ≤ n, 0 ≤ w ≤ 10^9). Возможны петли и кратные рёбра.
Вывод. n чисел через пробел: расстояние до вершин 1..n, для недостижимых -1.
Как подойти
Подсказки: 2
- Куча по расстоянию, пропускай устаревшие записи.
- Расстояния не влезут в Int.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.