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

    Дан ориентированный граф, в котором могут быть кратные ребра и петли. Каждое ребро имеет вес, выражающийся целым числом (возможно, отрицательным). Гарантируется, что циклы отрицательного веса отсутствуют.

    Требуется посчитать длины кратчайших путей от вершины номер 1 до всех остальных вершин.

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

    Программа получает сначала число N (1 <= N <= 100) – количество вершин графа и число M (0 <= M <= 10000) – количество ребер. В следующих строках идет M троек чисел, описывающих ребра: начало ребра, конец ребра и вес (вес – целое число от -100 до 100).

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

    Программа должна вывести N чисел – расстояния от вершины номер 1 до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число 30000.

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

    В Летней Компьютерной Школе (ЛКШ) построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход – в комнате N. Каждый ученик проходит лабиринт ровно один раз и попадает в ту или иную учебную группу в зависимости от количества набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

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

    Первая строка входных данных содержит целые числа N (1 <= N <= 2000) – количество комнат и M (1 <= M <= 10000) – количество дверей. В каждой из следующих M строк содержится описание двери – номера комнат, из которой она ведет и в которую она ведет (через дверь можно ходить только в одном направлении), а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

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

    Выведите ":)" – если можно получить неограниченно большой запас знаний, ":(" – если лабиринт пройти нельзя, и максимальное количество набранных знаний в противном случае.

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

    Дан ориентированный граф. Определить, есть ли в нем цикл отрицательного веса, и если да, то вывести его.

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

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

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

    В первой строке выведите "YES", если цикл существует, или "NO", в противном случае. При наличии цикла выведите во второй строке количество вершин в нем (считая одинаковые – первую и последнюю), а в третьей строке – вершины, входящие в этот цикл, в порядке обхода. Если циклов несколько, то  выведите любой из них.

    Примеры
    Входные данные
    3
    100000 100000 -51
    100  100000 100000
    100000 -50  100000
    
    Выходные данные
    YES
    4
    3 2 1 3
    
    ограничение по времени на тест
    0.0 second;
    ограничение по памяти на тест
    0 megabytes
    Максимальное время работы на одном тесте: 1 секунда

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

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

    Сначала вводятся два числа: N (от 1 до 100) и M – количество вершин и ребер графа соответственно. Далее идет M пар чисел, задающих ребра. Гарантируется, что граф связный.

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

    Выведите N-1 пару чисел – ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

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

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