Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах
    Кратчайшие пути в графе(116 задач)
    Обход в глубину(100 задач)
    Способы задания графа(54 задач)
    Минимальный каркас(12 задач)
    Потоки(21 задач)
    Паросочетания(17 задач)
    Эйлеров цикл(9 задач)
    Деревья(16 задач)
---> 319 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: << 3 4 5 6 7 8 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
    Города и дороги
      
    ограничение по времени на тест
    0.0 second;
    ограничение по памяти на тест
    0 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
    Светофорчики
      
    ограничение по времени на тест
    0.0 second;
    ограничение по памяти на тест
    0 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
    Цветной дождь
      
    ограничение по времени на тест
    0.0 second;
    ограничение по памяти на тест
    0 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
    #177
    Издевательство
      
    ограничение по времени на тест
    0.0 second;
    ограничение по памяти на тест
    0 megabytes
    Максимальное время работы на одном тесте: 1 секунда

    Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо. Через некоторое время он снова увидел голосующего Бормана, и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
     - Издевается! - подумал Борман.
     - Кольцевая! - догадался Штирлиц.

    В городе N площадей. Любые две площади соединены между собой ровно одной дорогой с двусторонним движением. В этом городе живет Штирлиц. У Штирлица есть хобби - он любит воскресным утром выйти из дома, сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно по трем площадям (то есть сначала он едет с какой-то площади на какую-то другую, потом - на третью, затем возвращается на начальную, и опять едет по этому маршруту). Он воображает, что где-то на этом пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова не закружится, и радуется...

    Естественно, что Штирлицу хочется проезжать мимо точки, в которой, как он воображает, стоит Борман, как можно чаще. Для этого, естественно, выбранный Штирлицем маршрут должен быть как можно короче. Напишите программу, которая выберет оптимальный для Штирлица маршрут.

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

    В первой строке задается  число N (3 <= N <= 100). В последующих строках содержится матрица NxN расстояний между площадями (число в позиции i,j обозначает длину дороги, соединяющей i-ую и j-ую площади). Все числа в матрице (кроме стоящих на главной диагонали) - натуральные, не превышающие 1000. Матрица симметрична относительно главной диагонали, на главной диагонали стоят 0.

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

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

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