e-olymp 625. Расстояние между вершинами

Задача с сайта e-olimp № 625.

Ссылка на засчитанное решение.

РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ

Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами.

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

Первая строка входного файла содержит натуральные числа N, M, S и F (N5000, M100000, 1S, FN, SF) — количество вершин и ребер графа а также номера вершин, длину пути между которыми требуется найти.

Следующие M строк содержат по три натуральных числа bi, ei и wi — номера концов i-ого ребра и его вес соответственно (1bi, eiN, 0wi100000).

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

Первая строка должна содержать одно натуральное число — вес минимального пути между вершинами S и F. Во второй строке через пробел выведите вершины на кратчайшем пути из S в F в порядке обхода. Если путь из S в F не существует, выведите -1.

Код программы:

После считывания входных данных создаем три массива. Массив вершин входящих в кратчайший путь, а также два массива для преобразования считанной матрицы в матрицу смежности  вершин графа. Далее с помощью алгоритма Дейкстра находим кратчайшее расстояние до каждой вершины и одновременно записываем в  массив [latex]h\left [ n \right ][/latex] вершины, через которые проходит кратчайший путь. Затем выводим расстояние до вершины [latex]f[/latex] если путь к ней существует, иначе печатаем: «-1». Далее выводим кратчайший маршрут между вершинами [latex]s[/latex] и [latex]f[/latex].

Related Images:

2 thoughts on “e-olymp 625. Расстояние между вершинами

    • Решение успешно проходит тесты на сайте e-olymp. Конечно, вполне возможно, что там слабые тесты.
      Если Вы считаете, что решение неверное, то нужно потрудиться и построить тест, который опровергает («ломает») решение. Тогда Вы действительно будете достойны хвалы, что и означает Ваше имя 🙂

Добавить комментарий