Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Алгоритм Флойда
---> 20 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 1 2 3 4 >> Отображать по:
#1332
Транзитивное замыкание
  

Невзвешенный ориентированный граф задан своей матрицей смежности. Требуется построить его транзитивное замыкание, то есть матрицу, в которой в \(i\)-й строке и \(j\)-м столбце находится 1, если от вершины \(i\) можно добраться до вершины \(j\), и 0 - иначе.

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

В первой строке дано число \(N\) (\(1 \le N \le 100\)) - число вершин в графе. Далее задана матрица смежности графа: в \(N\) строках даны по \(N\) чисел 0 или 1 в каждой. \(i\)-е число в \(i\)-й строке всегда равно 1.

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

Необходимо вывести матрицу транзитивного замыкания графа в формате, аналогичным формату матрицы смежности.

Примеры
Входные данные
4
1 1 0 0
0 1 1 0
1 0 1 0
0 0 1 1
Выходные данные
1 1 1 0 
1 1 1 0 
1 1 1 0 
1 1 1 1
#1334
Два профессора
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).

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

Необходимо вывести одно число - искомое расстояние.

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
3
Входные данные
3 0
Выходные данные
0
#1335
Столовая
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Сегодня у студентов праздник! В одном из новых зданий университета решили открыть столовую. Для этих целей требуется выбрать одно из зданий, в котором и будет располагаться столовая. Чтобы студенты как можно меньше отвлекались от учёбы, было решено выбрать такое здание, чтобы максимальное расстояние от него до всех остальных зданий было как можно меньше.

Помогите найти такое здание!

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

В первой строке находятся два числе \(N\) и \(M\) - количество зданий и количество дорог, соединяющих здания (\(1 \le N \le 100, 0 \le M \le \frac{N \cdot (N-1)}{2}\)). Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i\), \(e_i\), \(l_i\) - здания, в которых начинается и заканчивается дорога и длина дороги соответственно (\(1 \le s_i, e_i \le N, 0 \le l_i \le 100\), дороги двунаправленные).

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

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

Примеры
Входные данные
3 2
1 2 1
2 3 2
Выходные данные
2
Входные данные
3 1
1 2 10
Выходные данные
1
#1336
Опасный маршрут
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Профессор Флойд живёт в очень опасном районе города. Ежедневно бандиты грабят на улицах прохожих. Читая криминальную хронику, профессор Флойд вычислил вероятность быть ограбленным при проходе по каждой улице города.

Теперь он хочет найти наиболее безопасный путь от дома до университета, в котором он преподаёт. Иными словами, он хочет найти путь от дома до университета, для которого вероятность быть ограбленным минимальна.

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

В первой строке находятся два числа \(N\) и \(M\) - количество зданий и количество улиц, соединяющих здания (\(1 \le N \le 100, 1 \le M \le \frac{N \cdot (N-1)}{2}\)). В следующей строке находятся числа \(S\) и \(E\) -- номер дома, в котором живёт профессор и номер дома, в котором находится университет соответственно. Далее в \(M\) строках расположены описания дорог: 3 целых числа \(s_i, e_i, p_i\) - здания, в которых начинается и заканчивается дорога и вероятность в процентах быть ограбленным, пройдя по дороге соответственно (\(1 \le s_i, e_i \le N, 0 \le p_i \le 100\), дороги двунаправленные). Гарантируется, что существует хотя бы один путь от дома профессора до университета.

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

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

Примеры
Входные данные
3 3
1 3
1 2 20
1 3 50
2 3 20
Выходные данные
0.36
#1737
Заправки
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

При этом есть ещё канистра для бензина, куда входит столько же бензина, сколько входит в бак. В каждом городе можно заправить бак, залить бензин в канистру, залить и туда и туда, или же перелить бензин из канистры в бак.

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

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

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

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

Примеры
Входные данные
4
1 10 2 15
4
1 2 1 3 4 2 4 3
Выходные данные
2
Страница: << 1 2 3 4 >> Отображать по:
Выбрано
:
Отменить
|
Добавить в контест