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

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Найти длину кратчайшего пути из вершины s в вершину t.

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

В первой строке заданы три числа: число вершин в графе N ≤50, номера вершин s и t. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от 0 до 1000000, число -1 означает отсутствие соответствующего ребра. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – минимальную длину пути. Если пути не существует, выведите -1.

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

Дан ориентированный граф, рёбрам которого приписаны некоторые неотрицательные веса (длины). Надо найти две вершины, кратчайший путь между которыми имеет наибольшую длину.

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

В первой строке задано число вершин N ≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от от 0 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

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

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

Примеры
Входные данные
3
0 7 3
7 0 10
2 215 0
Выходные данные
10
#97
Самый короткий путь
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

Дан ориентированный полный граф, рёбрам которого приписаны некоторые веса (длины). Веса могут быть и положительные, и отрицательные, и нулевые. Нас интересует минимум длин всех возможных путей между всеми парами различных вершин этого графа. Нужно будет выяснить, существует ли этот минимум, и, если существует, вычислить его. (Минимума не существует в том случае, если в графе можно найти путь отрицательной длины, сколь угодно большой по модулю).

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

В первой строке задано число вершин N≤50. Далее идёт матрица смежности графа, то есть N строк, в каждой из которых записано N чисел. j-ое число в i-ой строке матрицы смежности задает длину ребра, ведущего из i-й вершину в j-ую. Длины могут принимать любые значения от -1000000 до 1000000. Гарантируется, что на главной диагонали матрицы стоят нули.

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

Выведите одно число – искомый минимум. Если его не существует, выведите  -1.

Примеры
Входные данные
3
0 42 18468 
6335 0 26501 
19170 15725 0
Выходные данные
42
Входные данные
3
0 -7 3
-2 0 10
2 215 0
Выходные данные
-1
#98
Есть ли цикл?
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes

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

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

В первой строке вводится число вершин N≤ 50. Далее в N строках следуют по N чисел, каждое из которых – 0 или 1. j-ое число в i-ой строке равно 1 тогда и только тогда, когда существует ребро, идущее из i-ой вершины в j-ую. Гарантируется, что на диагонали матрицы будут стоять нули.

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

Выведите 0, если в заданном графе цикла нет, и 1, если он есть.

Примеры
Входные данные
3
0 1 0
0 0 1
0 0 0
Выходные данные
0
Входные данные
3
0 1 0
0 0 1
1 0 0
Выходные данные
1
#171
Флойд - 1
  
ограничение по времени на тест
5.0 second;
ограничение по памяти на тест
64 megabytes

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

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

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

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

Выведите N строк по N чисел – матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно быть равно весу кратчайшего пути из вершины i в вершину j.

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