Алгоритм Дейкстры(33 задач)
    Алгоритм Флойда(20 задач)
    Обход в ширину(61 задач)
    Алгоритм Форда-Беллмана(6 задач)
---> 115 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 5 6 7 >> Отображать по:
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный взвешенный граф. Для него вам необходимо найти кратчайшее расстояние от вершины S до вершины F.

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

В первой строке входных данных содержатся три числа: N, S и F (1 <= N <= 100; 1 <= S, F <= N), где N – количество вершин графа. В следующих N строках записаны по N чисел – матрица смежности графа, где число в i-ой строке и j-ом столбце соответствует ребру из i в j: -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – наличие ребра данного веса. На главной диагонали матрицы всегда записаны нули.

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

Выведите искомое кратчайшее расстояние или -1, если пути между указанными вершинами не существует.

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

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

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

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

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

Примеры
Входные данные
5
3 6 1 7 6 
8
1 2
5 4
5 1
3 4
5 2
2 4
2 3
3 1
Выходные данные
3
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes

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

Марии Ивановне требуется добраться из деревни d в деревню v как можно быстрее (считается, что в момент времени 0 она находится в деревне d).

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

Сначала вводится число N – общее число деревень (1 <= N <= 100),  затем номера деревень d и v,  за ними следует количество автобусных рейсов R (0 <= R <= 10000). Далее идут описания автобусных рейсов. Каждый рейс задается номером деревни отправления, временем отправления, деревней назначения и временем прибытия (все времена – целые от 0 до 10000). Если в момент t пассажир приезжает в какую-то деревню, то уехать из нее он может в любой момент времени, начиная с t.

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

Выведите минимальное время, когда Мария Ивановна может оказаться в деревне v. Если она не сможет с помощью указанных автобусных рейсов добраться из d в v, выведите -1.

Примеры
Входные данные
3
1 3
4
1 0 2 5
1 1 2 3
2 3 3 5
1 1 3 10
Выходные данные
5
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы – всегда нули.

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

Выведите N строк по N чисел – матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

Примеры
Входные данные
4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0
Выходные данные
0 5 7 13 
12 0 2 8 
11 16 0 7 
4 9 11 0 
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится единственное число N (1 <= N <= 100) – количество вершин графа. В следующих N строках по N чисел задается матрица смежности графа, где -1 означает отсутствие ребра между вершинами, а любое неотрицательное число – присутствие ребра данного веса. На главной диагонали матрицы – всегда нули.

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

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

Примеры
Входные данные
6
0 6 8 -1 -1 -1
5 0 5 -1 -1 -1
1 7 0 -1 -1 -1
-1 -1 -1 0 6 -1
-1 -1 -1 -1 0 3
-1 -1 -1 2 -1 0
Выходные данные
9

Страница: << 1 2 3 4 5 6 7 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест