Алгоритмы на графах

337 задачвместе с подтемами
Число у задачи — рейтинг сложности, слово рядом — насколько она трудна по сравнению с другими задачами такого же типа. Шкалы задач с ответом и задач с кодом между собой не сравниваются. Рядом — счётчики попыток: ✓ успешные, ✗ неуспешные.
РейтингЛюбойдо 800800–11991200–15991600+Без рейтинга
СначалаПодходящиеНовыеПопулярныеПростыеСложные
Спасти новобранцев#29450
Группа солдат-новобранцев прибыла в армейскую часть N777. После знакомства с прапорщиком стало очевидно, что от работ на кухне по очистке картофеля спасти солдат может только чудо. 
 
Прапорщик, будучи не в состоянии запомнить фамилии, пронумеровал новобранцев от 1 до N. После этого он велел им построиться по росту (начиная с самого высокого). С этой несложной задачей могут справиться даже совсем необученные новобранцы, да вот беда, прапорщик уверил себя, что знает про некоторых солдат, кто из них кого выше, и это далеко не всегда соответствует истине. 
 
После трех дней обучения новобранцам удалось выяснить, что знает (а точнее, думает, что знает) прапорщик. Помогите им, используя эти знания, построиться так, чтобы товарищ прапорщик остался доволен. 
 
Входные данные 
Сначала на вход программы поступают числа N и M (1 < N <= 100, 1 <= M <= 5000) – количество солдат в роте и количество пар солдат, про которых прапорщик знает, кто из них выше. Далее идут эти пары чисел A и B по одной на строке (1 <= A,B <= N), что означает, что, по мнению прапорщика, солдат A выше, чем B. Не гарантируется, что все пары чисел во входных данных различны. 
 
Выходные данные 
В первой строке выведите "Yes" (если можно построиться так, чтобы прапорщик остался доволен) или "No" (если нет). После ответа "Yes" на следующей строке выведите N чисел, разделенных пробелами, - одно из возможных построений. 
Примеры
№ Входные данные Выходные данные
1
4 5 
1 2 
2 3 
3 4 
1 4 
4 1
 No

(c) Пасынков С., 2018 г.
Топологическая сортировка
✓ 29✗ 25500лёгкаяВойти и решать
Дороги королевства#29449
В одном королевстве n городов и m дорог. У каждого города есть своё название, состоящее из строчных латинских букв. Но королю не нравится, что есть дороги, ведущие из города с названием, являющимся лексикографически меньшим названия конечного. Он захотел это исправить, поменяв города, к которым относятся те или иные названия. Сам он, конечно, не справится. Помогите ему в этом! 
 
Формат файла входных данных: 
Первая строка содержит два целых числа n и m (2 <= n <= 1000; 1 <= M <= 10000) - количество городов и дорог в королевстве соответственно. 
 
Вторая строка содержит n строк, описывающих города. Описание задаётся строкой из строчных латинских букв - названия города. 
 
Далее в m строках перечислены дороги. Каждая дорога задаётся парой чисел - номерами начального и конечного городов соответственно. Дороги односторонние. 
 
Формат файла выходных данных: 
Вывести n чисел, каждое из которых обозначает номер названия, соответствующего i-ому городу. Если решения не существует, вывести -1.
 
Ввод Вывод
4 4 
aaa bacc cqe de 
1 4 
4 2 
4 3 
3 2
 1 4 3 2
3 3 
fi bru a 
1 2 
2 3 
3 1
 -1
(с) Филимонов И.
Топологическая сортировка
✓ 19✗ 8600лёгкаяВойти и решать
Хакер#27307
Однажды юный хакер Шалдыга Севин решил совершить дерзкое преступление - сменить имя своего друга Максима Никитина на сильвере, пока тот был в ЛКШ Зима (Ливневая Коробка Шредингера), чтобы Наталья Владимировна поставила ему двойку. Для этого Шалдыга решил заразить вирусом базу данных сильвера.
Однако юный хакер осознал одну проблему - он не знает, на каком именно компьютере лицея она хранится. Шалдыга не стал долго думать над этой проблемой и решил заразить все компьютеры в лицее (для надежности). Вирус работает так: раз в день он заражает все компьютеры, связанные с зараженными напрямую. Первый компьютер Шалдыге придется заразить лично, потому он может выбрать любой.
Хакер хочет узнать минимальное количество дней, которое понадобится для того, чтобы заразить все компьютеры лицея. Однако выяснилась еще одна проблема - эта задача легко решается с помощью БФСа, но написать его меньше чем за 15 дней невозможно, а Хакеру еще нужно сделать 200 номеров по математике. Поэтому Шалдыга попросил Вас сделать невозможное - написать программу, отвечающую на его вопрос, за время этого контеста.
 
Входные данные
В первой строке на вход подаются два числа N и M - количество компьютеров в лицее и соединений между ними соответственно. 1 <= N, M <= 100
В следущих M строках Вам даются описания соединений между компьютерами, а именно 2 чила U и V, которые означают, что компьютеры U и V соединены.
 
Выходные данные
Выведите ответ на вопрос Шалдыги

Ввод Вывод
6 9
1 2
1 3
2 4
2 6
3 4
3 5
4 5
4 6
5 6
 2



(с) Григорьев Е., 2017

графыОбход в ширину
✓ 4✗ 391 100средняяВойти и решать
Ski Course Rating#27302
Лыжный маршрут описывается M x N решеткой высот (1 <= M,N <= 500), каждая высота в интервале 0 .. 1,000,000,000.  
 
Некоторые из этих ячеек помечены как стартовые точки маршрута. Организаторы хотят вычислить рейтинг трудности каждой стартовой точке. Рейтинг трудности стартовой точки P – это минимальное число D такое, что корова сможет  успешно достичь как минимум T ячеек решётки  (1 <= T <= MN), если она стартует в P и может двигаться в соседнюю ячейку (на север, юг, запад или восток), только если абсолютная величина разности высот в этих ячейках не превосходит D. 
 
Вычислите рейтинг трудности для каждой стартовой точки и выведите их сумму.
 
 
INPUT FORMAT:
 
* Строка 1: Целые числа M, N, T.
 
* Строки 2..1+M: Каждая из этих M строк содержит N целых высот.
 
* Строки 2+M..1+2M: Каждая из этих M строк содержит N величин равных 0 или 1, где 1 означает, что это ячейка – стартовая точка


OUTPUT FORMAT:
 
* Строка 1: Сумма рейтингов трудности всех стартовых точек (заметим, что это число может не поместиться в 32-битное целое, даже если каждый рейтинг в отдельности поместится).
 

INPUT DETAILS:
 
Местность описывается решеткой из 3 х 5 высот.
Верхняя левая и правая нижняя ячейки являются стартовыми точками.
Из каждой стартовой точки мы должны быть способны добраться до 10 ячеек.
 
OUTPUT DETAILS:
Рейтинг трудности верхнего левого угла равен 4.
Рейтинг трудности правого нижнего угла равен 20.
 
Ввод Вывод
3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1
 24

 
Бинарный поиск по ответуграфыПоиск компонент связности
—Войти и решать
Отрицательный цикл#27277
Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса.

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

Примеры
№ Входные данные Выходные данные
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
 YES
Алгоритм Флойда
✓ 211✗ 398500лёгкаяВойти и решать
Рейсы во времени#27276

Между \(N\) населенными пунктами совершаются пассажирские рейсы на машинах времени.

В момент времени 0 вы находитесь в пункте \(A\). Вам дано расписание рейсов. Требуется оказаться в пункте \(B\) как можно раньше (то есть в наименьший возможный момент времени).

При этом разрешается делать пересадки с одного рейса на другой. Если вы прибываете в некоторый пункт в момент времени \(T\), то вы можете уехать из него любым рейсом, который отправляется из этого пункта в момент времени \(T\) или позднее (но не раньше).

Формат входных данных
Первая строка содержит число \(N\) — количество населенных пунктов (\(1 \le N \le 1000\)). Вторая строка содержит два числа \(A\) и \(B\) — номера начального и конечного пунктов. Третья строка содержит число \(K\) — количество рейсов (\(0 \le K \le 1000\)). Следующие \(K\) строк содержит описания рейсов, по одному на строке. Каждое описание представляет собой четверку целых чисел. Первое число каждой четверки задает номер пункта отправления, второе — время отправления, третье — пункт назначения, четвертое — время прибытия. Номера пунктов — натуральные числа из диапазона от 1 до \(N\). Пункт назначения и пункт отправления могут совпадать. Время измеряется в некоторых абсолютных единицах и задается целым числом, по модулю не превышающим \(10^9\). Поскольку рейсы совершаются на машинах времени, то время прибытия может быть как больше времени отправления, так и меньше, или равным ему.

Гарантируется, что входные данные таковы, что добраться из пункта \(A\) в пункт \(B\) всегда можно.

Формат выходных данных
Выведите минимальное время, когда вы сможете оказаться в пункте \(B\).

Алгоритм Флойда
✓ 10✗ 321 000средняяВойти и решать
Авиаперелеты#27275
Профессору Форду необходимо попасть на международную конференцию. Он хочет потратить на дорогу наименьшее количество денег, поэтому решил, что будет путешествовать исключительно ночными авиарейсами (чтобы не тратиться на ночевку в отелях), а днем будет осматривать достопримечательности тех городов, через которые он будет проезжать транзитом. Он внимательно изучил расписание авиаперелетов и составил набор подходящих авиарейсов, выяснив, что перелеты на выбранных направлениях совершаются каждую ночь и за одну ночь он не сможет совершить два перелета.
 
Теперь профессор хочет найти путь наименьшей стоимости, учитывая что до конференции осталось K ночей (то есть профессор может совершить не более K перелетов).
 
Входные данные
В первой строке находятся числа N (количество городов), M (количество авиарейсов), K (количество оставшихся ночей), S (номер города, в котором живет профессор), F (номер города, в котором проводится конференция).
 
Ограничения: 2≤N≤100, 1≤M≤105, 1≤K≤100, 1≤S≤N, 1≤F≤N.
 
Далее идет M строк, задающих расписание авиарейсов. i-я строка содержит три натуральных числа: Si, Fi и Pi, где Si - номер города, из которого вылетает i-й рейс, Fi - номер го-рода, в который прилетает i-й рейс, Pi - стоимость перелета i-м рейсом. 1≤Si≤N, 1≤Fi≤N, 1≤Pi≤106.
 
Выходные данные
Выведите одно число - минимальную стоимость пути, подходящего для профессора. Если профессор не сможет за K ночей добраться до конференции, выведите число -1.

Ввод Вывод
4 5 2 1 4
1 2 1
2 3 1
3 4 1
1 3 3 
1 4 5
 4

Алгоритм Форда-Беллманакратчайшие пути
✓ 5✗ 40900средняяВойти и решать
Количество релаксаций#27274
Дан взвешенный ориентированный граф. Необходимо найти минимальное количество фаз с релаксациями в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

Входные данные
Программа получает на вход одно число количество вершин n (2 ≤ n ≤ 100) и количество ребер m (2 ≤m ≤ 10 000). В следующих m строках вводятся три числа: a, b и c, где a и b – начало ребра и его конец, а c – вес ребра (1 ≤ a, b ≤ n, 1 ≤ c ≤ 10 000).

Выходные данные
Программа должна вывести единственное целое число - минимальное количество релаксаций в работе алгоритма Форда-Беллмана при нахождении кратчайшего пути от вершины 1. 

Ввод Вывод
4 3
1 2 1 
2 3 1
3 4 1
 1
4 3
2 3 1
1 2 1
1 3 4
 2


(с) Шалдин В., 2017г.

Алгоритм Форда-Беллмана
✓ 28✗ 35500лёгкаяВойти и решать
Домой на электричках#27273
Одна из команд-участниц олимпиады решила вернуться домой на электричках. При этом ребята хотят попасть домой как можно раньше. К сожалению, не все электрички идут от города, где проводится олимпиада, до станции, на которой живут ребята. И, что еще более обидно, не все электрички, которые идут мимо их станции, останавливаются на ней (равно как вообще, электрички останавливаются далеко не на всех станциях, мимо которых они идут).
 
Все станции на линии пронумерованы числами от 1 до N. При этом станция номер 1 находится в городе, где проводится олимпиада, и в момент времени 0 ребята приходят на станцию. Станция, на которую нужно попасть ребятам, имеет номер E.
 
Напишите программу, которая по данному расписанию движения электричек вычисляет минимальное время, когда ребята могут оказаться дома.
 
Формат входных данных
Во входных данных записаны сначала числа N (2 ≤ N ≤ 100) и E (2 ≤ E ≤ N). Затем записано число M (0 ≤ M ≤ 100), обозначающее число рейсов электричек. Далее идет описание M рейсов электричек. Описание каждого рейса электрички начинается с числа Ki (2 ≤ K ≤ N) — количества станций, на которых она останавливается, а далее следует Ki пар чисел, первое число каждой пары задает номер станции, второе — время, когда электричка останавливается на этой станции (время выражается целым числом из диапазона от 0 до 109). Станции внутри одного рейса упорядочены в порядке возрастания времени. В течение одного рейса электричка все время движется в одном направлении — либо от города, либо к городу.
 
Формат выходных данных
Выведите одно число — минимальное время, когда ребята смогут оказаться на своей станции. Если существующими рейсами электричек они добраться не смогут, выведите –1.
 
Алгоритм Дейкстры
✓ 167✗ 174700средняяВойти и решать
Лабиринт знаний#27272
В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.
 
Входные данные:
Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.
 
Выходные данные:
Выведите ":)" – если можно получить неограниченно большой запас знаний, ":(" – если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

Примеры
№ Входные данные Выходные данные
1
2 2
1 2 3
1 2 7
 7

 
Алгоритм Форда-Беллмана
✓ 14✗ 2101 000средняяВойти и решать
Форд-Беллман - 2#27271
В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле \(wt(i,j)=(179i+719j)\ mod \ 1000 - 500\). Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.
 
Входные данные:
Программа получает на вход одно число n (2≤n≤13000).
 
Выходные данные:
Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном  графе.

Примеры
№ Входные данные Выходные данные
1 2 117
2 3 -164
Алгоритм Форда-Беллмана
✓ 42✗ 271700средняяВойти и решать
Отрицательный цикл-2#27269
Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.
 
Входные данные
В первой строке содержится число N (1 <= N <= 100) – количество вершин графа. В следующих N строках находится по N чисел – матрица смежности графа. Веса ребер по модулю меньше 100000. Если ребра нет, соответствующее значение равно 100000.
 
Выходные данные
В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то  выведите любой из них.

Примеры
№ Входные данные Выходные данные
1
3
100000 100000 -51
100  100000 100000
100000 -50  100000
YES
4
3 2 1 3
Алгоритм Флойда
✓ 129✗ 559800средняяВойти и решать
Форд-Беллман: Начало (C++)#27268
Дополните программу, чтобы она верно решала следующую задачу.

Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
 
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
 
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.
 
Примеры
№ Входные данные Выходные данные
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Алгоритм Форда-Беллмана
✓ 81✗ 184500лёгкаяВойти и решать
Форд-Беллман#27267
Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.
 
Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.
 
Входные данные
Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).
 
Выходные данные
Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

Примеры
№ Входные данные Выходные данные
1
6 4
1 2 10
2 3 10
1 3 100
4 5 -10
 0 10 20 30000 30000 30000 
Алгоритм Форда-Беллмана
✓ 129✗ 84300лёгкаяВойти и решать
Pink Floyd#27233
Группа Pink Floyd собирается дать новый концертный тур по всему миру. По предыдущему опыту группа знает, что солист Роджер Уотерс постоянно нервничает при перелетах. На некоторых маршрутах он теряет вес от волнения, а на других - много ест и набирает вес.
 
Известно, что чем больше весит Роджер, тем лучше выступает группа, поэтому требуется спланировать перелеты так, чтобы вес Роджера на каждом концерте был максимально возможным. Группа должна посещать города в том же порядке, в котором она дает концерты. При этом между концертами группа может посещать промежуточные города.
 
Входные данные
Первая строка входного файла содержит три натуральных числа n, m и k - количество городов в мире, количество рейсов и количество концертов, которые должна дать группа соответственно (n≤100, m≤104, 2≤k≤104). Города пронумерованы числами от 1 до n. Следующие m строк содержат описание рейсов, по одному на строке. Рейс номер i описывается тремя числами bi, ei и wi - номер начального и конечного города рейса и предполагаемое изменение веса Роджера в миллиграммах (1≤bi,ei≤n, −105≤wi≤105). Последняя строка содержит числа a1, a2, ..., ak - номера городов, в которых проводятся концерты. В начале концертного тура группа находится в городе a1.Гарантируется, что группа может дать все концерты.
 
Выходные данные
Первая строка выходного файла должна содержать число s - количество рейсов, которые должна сделать группа. Вторая строка должна содержать s чисел - номера используемых рейсов. Если существует такая последовательность маршрутов между концертами, что Роджер будет набирать вес неограниченно, то первая строка выходного файла должна содержать строку “infinitely kind”.

Ввод Вывод
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 -10
1 3 1 2 4
6
5 6 5 7 2 3 
4 8 5
1 2 -2
2 3 3
3 4 -5
4 1 3
1 3 2
3 1 -2
3 2 -3
2 4 10
1 3 1 2 4
 infinitely kind

 

Алгоритм Флойдаграфыкратчайшие пути
✓ 24✗ 76800средняяВойти и решать
Опасный маршрут#27232
Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.
 
Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.
 
Входные данные
В первой строке находятся два числа N и M - количество зданий и количество улиц, соединяющих здания (1<=N<=100, 1<=M<= (N*(N−1))/2. В следующей строке находятся числа S и E -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в M строках расположены описания дорог: 3 целых числа sieipi - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (1<=si, ei<=N, 0<=pi<=100 , дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.
 
Выходные данные
Необходимо вывести одно число - минимальную возможную вероятность быть ограбленным. Выведите ответ с максимально возможной точностью.

Ввод Вывод
3 3
1 3
1 2 20
1 3 50
2 3 20
 0.36

 

Алгоритм Дейкстрыкратчайшие пути
✓ 14✗ 12700средняяВойти и решать
Столовая#27231
Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.
 
Помогите найти такое здание!
 
Входные данные
В первой строке находятся два числе N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0 <=M<=(N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа si, ei, li - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=si, ei<=N, 0<=li,=100, дороги двунаправленные).
 
Выходные данные
Необходимо вывести одно число - номер искомого здания. Если есть несколько зданий удовлетворяющих поставленным критериям, выберите среди них здание с наименьшим номером.

Ввод Вывод
3 2
1 2 1
2 3 2
 2
3 1
1 2 10
 1

Алгоритм Флойдакратчайшие пути
✓ 13✗ 53800средняяВойти и решать
Два профессора#27230
Профессор Флойд и профессор Дейкстра ненавидят друг друга. После переезда университета во вновь отстроенный университетский городок они потребовали себе кабинеты в зданиях, максимально удалённых друг от друга. Вам поручено найти расстояние между двумя такими зданиями.
 
Иными словами, требуется найти два здания, кратчайший путь между которыми наибольший среди всех пар зданий, и вывести длину этого пути. Так как профессорам иногда все же нужно встречаться, путь между выбранными зданиями должен существовать.
 
Входные данные
В первой строке находятся два числа N и M - количество зданий и количество дорог, соединяющих здания (1<=N<=100, 0<=M<= (N(N−1))/2. Далее в M строках расположены описания дорог: 3 целых числа si, ei, li - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (1<=si, ei<=N, 0<=li<=100, дороги двунаправленные).
 
Выходные данные
Необходимо вывести одно число - искомое расстояние.

Ввод Вывод
3 2
1 2 1
2 3 2
 3
3 0 0

Алгоритм Флойда
✓ 25✗ 75700средняяВойти и решать
Флойд: Начало №2#27228
Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.
 
Входные данные
В первой строке вводится единственное число 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 

Алгоритм Флойда
✓ 39✗ 21300лёгкаяВойти и решать
Флойд №2#27227
Дан ориентированный взвешенный граф. Вам необходимо найти пару вершин, кратчайшее расстояние от одной из которых до другой максимально среди всех пар вершин.
 
Входные данные
В первой строке вводится единственное число 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

Алгоритм Флойдакратчайшие пути
✓ 42✗ 30300лёгкаяВойти и решать
Поделиться
Класснуть