e-olymp 1388. Заправки

Задача с сайта e-olymp.com.

Условие задачи

В стране n городов, некоторые из которых соединены между собой дорогами. Для того, чтобы проехать по одной дороге требуется один бак бензина. В каждом городе бак бензина имеет разную стоимость. Вам требуется добраться из первого города в n-ый, потратив как можно меньшее количество денег.

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

Сначала идет количество городов n (1 ≤ n ≤ 100), затем идет n чисел, i-ое из которых задает стоимость бензина в i-ом городе (все числа целые из диапазона от 0 до 100). Затем идет количество дорог m в стране, далее идет описание самих дорог. Каждая дорога задается двумя числами — номерами городов, которые она соединяет. Все дороги двухсторонние (то есть по ним можно ездить как в одну, так и в другую сторону); между двумя городами всегда существует не более одной дороги; не существует дорог, ведущих из города в себя.

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

Выведите одно число — суммарную стоимость маршрута или -1, если добраться невозможно.

Тесты

Входные данные Выходные данные
1 4
1 10 2 15
4
1 2 1 3 4 2 4 3
3
2 4
1 10 2 15
0
-1
3 5
1 2 3 4 5
4
1 2 2 3 3 4 4 5
10

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

Описание

Оптимальную стоимость маршрута будем находить по алгоритму Дейкстры. Цены на бензин в i-ом городе хранятся в массиве price. Минимальные стоимости маршрутов к каждому из городов хранятся в массиве distance, изначально все маршруты принимаем бесконечно дорогими. Кроме того, для хранения информации о том, был ли рассмотрен i-й город, используется массив used. Сам граф представляется в виде списка смежности. Для этого используется массив векторов graph. Если в итоге стоимость маршрута до целевого города осталась бесконечной, значит, пути к нему не существует, и выводится -1. Иначе выводится эта стоимость.

Код на ideone.com.

Засчитанное решение на e-olymp.com.

e-olymp 5072. Подсчет количества ребер

Постановка задачи

Ссылка на задачу с сайта e-olymp

Ориентированный граф задан матрицей смежности. Найдите количество ребер в графе.

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

Входной файл содержит число [latex]n(1 \leq n \leq 100)[/latex] — число вершин в графе, и затем [latex]n[/latex] строк по [latex]n[/latex] чисел, каждое из которых равно [latex]0[/latex] или [latex]1[/latex] — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Тест

Значения Результат
1 3
0 1 1
1 0 1
0 1 1
6

Решение

Ссылка на решение задания с сайта e-olymp

Ссылка на решение задания на онлайн компиляторе Ideone.com

Описание решения

Объявляем переменную  n типа int. Чтобы найти количество ребер в графе, вводим в двух циклах каждый элемент матрицы смежности и если значение больше нуля, то увеличиваем сумму.

e-olymp 975. Флойд

Задача

Постановка задачи на e-olymp.

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

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

В первой строке содержится количество вершин графа [latex]n[/latex] [latex](1 \leq n \leq 100)[/latex]. В следующих [latex]n[/latex] строках находится по [latex]n[/latex] чисел, которые задают матрицу смежности графа. В ней -1 означает отсутствие ребра между вершинами, а любое неотрицательное число — присутствие ребра данного веса. На главной диагонали матрицы всегда расположены нули.

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

Вывести искомое максимальное кратчайшее расстояние.

Тесты

n matrix Результат
1 4 0   5   9   -1
-1   0   2   8
-1   -1   0   7
4   -1  -1   0
16
2 3 0   -1   2
2    0  -1
4    1   0
4
3 5 0  -1  -1  3  4
2  0  3  -1  4
-1  4  0  -1  4
3  -1  2  0  1
1  1  -1  -1  0
8

Ссылка на успешно пройденные тесты на сайте e-olymp.

Решение

Проверить работу кода можно в облаке по ссылке — Ideone.

Пояснения

Данная задача решается при использовании алгоритма Флойда-Уоршелла, суть которого состоит в нахождении длин кратчайших путей между всеми парами вершин во взвешенном ориентированном графе. Код данного алгоритма можно наблюдать в цикле по [latex]i[/latex], в котором имеются два вложенных цикла по [latex]j[/latex] и по [latex]k[/latex]. Здесь мы проходим по элементам матрицы смежности графа, проверяя существует ли ребро между вершинами. Далее следуя алгоритму Флойда выполняем следующее действие — с помощью функции Math.min()  находим минимальный путь из одной вершины в другую, записывая  его в матрицу. По нахождении всех кратчайших путей, находим максимальный из них, и выводим его в консоль.