Темы --> Информатика --> Алгоритмы --> Алгоритмы на графах --> Кратчайшие пути в графе --> Алгоритм Форда-Беллмана
---> 6 задач <---
Источники
    Личные олимпиады(938 задач)
    Командные олимпиады(684 задач)
Страница: 1 2 >> Отображать по:
#178
Форд-Беллман
  
ограничение по времени на тест
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
#179
Лабиринт знаний
  
ограничение по времени на тест
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
#180
Цикл
  
ограничение по времени на тест
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
#524
Рейсы во времени
  
Источники: [ Командные олимпиады, ВКОШП, 2003, Задача I ]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
В ориентированном графе ребро задается 4 числами: начальной и конечной вершинами, временем отправления и временем прибытия. Причем, время прибытия может быть меньше либо равно времени отправления.

Между \(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\).

Примеры
Входные данные
2
1 1
2
1 1 2 10
1 10 1 9
Выходные данные
0
Входные данные
1
1 1
3
1 3 1 -5
1 -5 1 -3
1 -4 1 -10
Выходные данные
-10
Входные данные
5
1 2
6
1 0 3 10
4 2 2 -10
4 14 2 -7
3 10 2 10
2 0 4 2
3 10 4 12
Выходные данные
-10
#1994
Форд-Беллман - 2
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
16 megabytes

В ориентированном взвешенном графе вершины пронумерованы числами от 1 до n. Если i<j, то существует ребро из вершины i в вершину j, вес которого определяется по формуле wt(i,j)=(179i+719j) mod 1000 - 500. Определите вес кратчайшего пути, ведущего из вершины 1 в вершину n.

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

Программа получает на вход одно число n (2≤n≤13000).

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

Программа должна вывести единственное целое число - вес кратчайшего пути из вершины 1 в вершину n в описанном  графе.

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