Темы --> Информатика
    Язык программирования(952 задач)
    Алгоритмы(1657 задач)
    Структуры данных(279 задач)
    Интерактивные задачи(17 задач)
    Другое(54 задач)
---> 2656 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 32 33 34 35 36 37 38 >> Отображать по:
#172
Флойд - 2
  
ограничение по времени на тест
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
#173
Флойд - существование
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

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

Комментарий: Кратчайший путь может не существовать по двум причинам:

  • Нет ни одного пути
  • Есть пути сколь угодно маленького веса

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

    В первой строке входного файла записано единственное число: \(N\) (\(1\leq N\leq 100\)) — количество вершин графа. В следующих \(N\) строках по \(N\) чисел — матрица смежности графа (\(j\)-е число в \(i\)-й строке соответствует весу ребра из вершины \(i\) в вершину \(j\)): число 0 обозначает отсутствие ребра, а любое другое число — наличие ребра соответствующего веса. Все числа по модулю не превышают 100.

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

    Выведите \(N\) строк по \(N\) чисел. \(j\)-е число в \(i\)-й строке должно соответствовать кратчайшему пути из вершины \(i\) в вершину \(j\). Число должно быть равно 0, если пути не существует, 1, если существует кратчайший путь, и 2, если пути существуют, но бывают пути сколь угодно маленького веса.

    Примеры
    Входные данные
    5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0
    Выходные данные
    1 1 1 0 0 
1 1 1 0 0 
1 1 1 0 0 
0 0 0 2 2 
0 0 0 2 2
    #174
    Города и дороги
      
    ограничение по времени на тест
    1.0 second;
    ограничение по памяти на тест
    64 megabytes
    Максимальное время работы на одном тесте: 5 секунд

    В галактике "Milky Way" на планете "Neptune" есть N городов, некоторые из которых соединены дорогами. Император "Maximus" галактики "Milky Way" решил провести инвентаризацию дорог на планете "Neptune". Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.

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

    В первой строке  задается число N (0 ≤ N ≤ 100). В следующих N строках содержится по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

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

    Выведите одно число – количество дорог на планете "Neptune".

    Примеры
    Входные данные
    5
0 1 0 0 0 
1 0 1 1 0 
0 1 0 0 0 
0 1 0 0 0 
0 0 0 0 0
    Выходные данные
    3
    #175
    Светофорчики
      
    ограничение по времени на тест
    1.0 second;
    ограничение по памяти на тест
    64 megabytes
    Максимальное время работы на одном тесте: 5 секунд

    В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

    Первая строка входных данных содержит два числа N и M (0 < N ≤ 100, 0 ≤ M ≤ N*(N – 1)/2). В каждой из следующих M строк записаны по два числа i и j (1 ≤ i,j ≤ N), которые означают, что перекрестки i и j соединены тоннелем.

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

    Требуется вывести N чисел: k-ое число означает количество светофоров на k-ом перекрестке.

    Примечание. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

    Примеры
    Входные данные
    7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3
    Выходные данные
    3 3 2 2 5 2 3
    #176
    Цветной дождь
      
    ограничение по времени на тест
    1.0 second;
    ограничение по памяти на тест
    64 megabytes
    Максимальное время работы на одном тесте: 5 секунд

    В Банановой республике очень много холмов, соединенных мостами. На химическом заводе произошла авария, в результате чего испарилось экспериментальное удобрение "зован". На следующий день выпал цветной дождь, причем он прошел только над холмами. В некоторых местах падали красные капли, в некоторых – синие, а в остальных – зеленые, в результате чего холмы стали соответствующего цвета. Президенту Банановой республики это понравилось, но ему захотелось покрасить мосты между вершинами холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют. К сожалению, если холмы разного цвета, то покрасить мост таким образом не удастся. Посчитайте количество таких "плохих" мостов.

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

    В  первой строке входных данных содержится число N (0 < N ≤ 100) – количество холмов. Далее идет матрица смежности, описывающая наличие мостов между холмами (1 – мост есть, 0 – нет). После матрицы смежности идёт пустая строка, и в последней строке записано N чисел, обозначающих цвет холмов: 1 – красный; 2 – синий; 3 – зеленый.

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

    Выведите одно число – количество "плохих" мостов.

    Примеры
    Входные данные
    7
0 1 0 0 0 1 1 
1 0 1 0 0 0 0 
0 1 0 0 1 1 0 
0 0 0 0 0 0 0 
0 0 1 0 0 1 0 
1 0 1 0 1 0 0 
1 0 0 0 0 0 0 

1 1 1 1 1 3 3
    Выходные данные
    4
    Страница: << 32 33 34 35 36 37 38 >> Отображать по:
    Выбрано
    :
    Отменить
    |
    Добавить в контест