Примеры из веба для сверки ответов:

Источник

Источник

Источник

Таблица длин маршрутов

Отображать дерево

12345
1
2
3
4
5

Легенда узла: Номер шага обработки(Строка:Колонка)Стоимость

При клике на узел с номером обработки можно увидеть лог вычислений на данном этапе

(Для подбробного решения выберите нужный этап на дереве)

Ответ: путь:1=>5=>3=>4=>2=>1 длина: 190

Время:0.0026140213012695

Вычитание минимумов по строке

12345
1INF35451733
20INF355177
3456INF3389
4268887INF89
597933691INF

Нахождение минимальных по строкам

Мнимальные по строкам:17 0 4 26 36

Почти новая мин граница 83

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 18 0 0 16

Новая мин граница 117

Результат вычитания минимумов по столбцам

12345
1INF02800
20INF355161
3034INF2969
404461INF47
56139055INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=34
(1:4)=29
(1:5)=47
(2:1)=35
(3:1)=29
(4:1)=44
(5:3)=67

Конец подсчета штрафов у нулей

Максимумы по строкам:47 35 29 44 67

Максимальная степень 0 находятся на позициях (5:3)

Нули на предыдущих этапах:(5:3)

Начинаем разделение

12345
1INF02800
20INF355161
3034INF2969
404461INF47
56139055INF

(5:3)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (5,3)

12345
1INF02800
20INF355161
3034INF2969
404461INF47
56139INF55INF

Вычитание минимумов по строке

12345
1INF02800
20INF355161
3034INF2969
404461INF47
56139INF55INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 39

Почти новая мин граница 156

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 28 0 0

Новая мин граница 184

Результат вычитания минимумов по столбцам

12345
1INF0000
20INF75161
3034INF2969
404433INF47
5220INF16INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=0
(1:3)=7
(1:4)=16
(1:5)=47
(2:1)=7
(3:1)=29
(4:1)=33
(5:2)=16

Конец подсчета штрафов у нулей

Максимумы по строкам:47 7 29 33 16

Максимальная степень 0 находятся на позициях (1:5)

Удаление из матрицы 5:3

12345
1INF02800
20INF355161
3034INF2969
404461INF47
56139055INF

Результат удаления из матрицы 5:3

1245
1INF000
20INF5161
30342969
4044INF47

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (5,3)

1245
1INF000
20INF5161
303429INF
4044INF47

Вычитание минимумов по строке

1245
1INF000
20INF5161
303429INF
4044INF47

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0

Почти новая мин граница 117

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 117

Результат вычитания минимумов по столбцам

1245
1INF000
20INF5161
303429INF
4044INF47

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=34
(1:4)=29
(1:5)=47
(2:1)=51
(3:1)=29
(4:1)=44

Конец подсчета штрафов у нулей

Максимумы по строкам:47 51 29 44

Максимальная степень 0 находятся на позициях (2:1)

Граница у несодержащего ребро (5,3):184 у содержащего117

Нули на предыдущих этапах:(2:1) (5:3)

Начинаем разделение

1245
1INF000
20INF5161
303429INF
4044INF47

(2:1)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (2,1)

1245
1INF000
2INFINF5161
303429INF
4044INF47

Вычитание минимумов по строке

1245
1INF000
2INFINF5161
303429INF
4044INF47

Нахождение минимальных по строкам

Мнимальные по строкам:0 51 0 0

Почти новая мин граница 168

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 168

Результат вычитания минимумов по столбцам

1245
1INF000
2INFINF010
303429INF
4044INF47

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=34
(1:4)=0
(1:5)=10
(2:4)=10
(3:1)=29
(4:1)=44

Конец подсчета штрафов у нулей

Максимумы по строкам:34 10 29 44

Максимальная степень 0 находятся на позициях (4:1)

Удаление из матрицы 2:1

1245
1INF000
20INF5161
303429INF
4044INF47

Результат удаления из матрицы 2:1

245
1000
33429INF
444INF47

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (2,1)

245
1INF00
33429INF
444INF47

Вычитание минимумов по строке

245
1INF00
33429INF
444INF47

Нахождение минимальных по строкам

Мнимальные по строкам:0 29 44

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0

Новая мин граница 190

Результат вычитания минимумов по столбцам

245
1INF00
350INF
40INF3

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:4)=0
(1:5)=3
(3:4)=5
(4:2)=8

Конец подсчета штрафов у нулей

Максимумы по строкам:3 5 8

Максимальная степень 0 находятся на позициях (4:2)

Граница у несодержащего ребро (2,1):168 у содержащего190

Нули на предыдущих этапах:(4:1) (2:1) (5:3)

Начинаем разделение

1245
1INF000
2INFINF010
303429INF
4044INF47

(4:1)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (4,1)

1245
1INF000
2INFINF010
303429INF
4INF44INF47

Вычитание минимумов по строке

1245
1INF000
2INFINF010
303429INF
4INF44INF47

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 44

Почти новая мин граница 212

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0

Новая мин граница 212

Результат вычитания минимумов по столбцам

1245
1INF000
2INFINF010
303429INF
4INF0INF3

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=0
(1:4)=0
(1:5)=3
(2:4)=10
(3:1)=29
(4:2)=3

Конец подсчета штрафов у нулей

Максимумы по строкам:3 10 29 3

Максимальная степень 0 находятся на позициях (3:1)

Удаление из матрицы 4:1

1245
1INF000
2INFINF010
303429INF
4044INF47

Результат удаления из матрицы 4:1

245
1000
2INF010
33429INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (4,1)

245
10INF0
2INF010
33429INF

Вычитание минимумов по строке

245
10INF0
2INF010
33429INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 29

Почти новая мин граница 197

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0

Новая мин граница 197

Результат вычитания минимумов по столбцам

245
10INF0
2INF010
350INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=5
(1:5)=10
(2:4)=10
(3:4)=5

Конец подсчета штрафов у нулей

Максимумы по строкам:10 10 5

Максимальная степень 0 находятся на позициях (1:5)

Граница у несодержащего ребро (4,1):212 у содержащего197

Нули на предыдущих этапах:(1:5) (5:3)

Начинаем разделение

12345
1INF0000
20INF75161
3034INF2969
404433INF47
5220INF16INF

(1:5)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,5)

12345
1INF000INF
20INF75161
3034INF2969
404433INF47
5220INF16INF

Вычитание минимумов по строке

12345
1INF000INF
20INF75161
3034INF2969
404433INF47
5220INF16INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0 0

Почти новая мин граница 184

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 0 0 47

Новая мин граница 231

Результат вычитания минимумов по столбцам

12345
1INF000INF
20INF75114
3034INF2922
404433INF0
5220INF16INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:2)=0
(1:3)=7
(1:4)=16
(2:1)=7
(3:1)=22
(4:1)=0
(4:5)=14
(5:2)=16

Конец подсчета штрафов у нулей

Максимумы по строкам:16 7 22 14 16

Максимальная степень 0 находятся на позициях (3:1)

Удаление из матрицы 1:5

12345
1INF0000
20INF75161
3034INF2969
404433INF47
5220INF16INF

Результат удаления из матрицы 1:5

1234
20INF751
3034INF29
404433INF
5220INF16

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,5)

1234
20INF751
3034INF29
404433INF
5INF0INF16

Вычитание минимумов по строке

1234
20INF751
3034INF29
404433INF
5INF0INF16

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 0 0

Почти новая мин граница 184

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0 7 16

Новая мин граница 207

Результат вычитания минимумов по столбцам

1234
20INF035
3034INF13
404426INF
5INF0INF0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(2:1)=0
(2:3)=26
(3:1)=13
(4:1)=26
(5:2)=34
(5:4)=13

Конец подсчета штрафов у нулей

Максимумы по строкам:26 13 26 34

Максимальная степень 0 находятся на позициях (5:2)

Граница у несодержащего ребро (1,5):231 у содержащего207

Нули на предыдущих этапах:(4:2) (2:1) (5:3)

Начинаем разделение

245
1INF00
350INF
40INF3

(4:2)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (4,2)

245
1INF00
350INF
4INFINF3

Вычитание минимумов по строке

245
1INF00
350INF
4INFINF3

Нахождение минимальных по строкам

Мнимальные по строкам:0 0 3

Почти новая мин граница 193

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:5 0 0

Новая мин граница 198

Результат вычитания минимумов по столбцам

245
1INF00
300INF
4INFINF0

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:4)=0
(1:5)=0
(3:2)=0
(3:4)=0
(4:5)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0 0

Максимальная степень 0 находятся на позициях (1:4)

Удаление из матрицы 4:2

245
1INF00
350INF
40INF3

Результат удаления из матрицы 4:2

45
100
30INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (4,2)

45
100
30INF

Вычитание минимумов по строке

45
100
30INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 190

Результат вычитания минимумов по столбцам

45
100
30INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:4)=0
(1:5)=0
(3:4)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0

Максимальная степень 0 находятся на позициях (1:4)

Граница у несодержащего ребро (4,2):198 у содержащего190

Нули на предыдущих этапах:(1:4) (4:2) (2:1) (5:3)

Начинаем разделение

45
100
30INF

(1:4)

Поиск циклов

Цикл найден. уничтожен [4][1]

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,4)

45
1INF0
30INF

Вычитание минимумов по строке

45
1INF0
30INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 190

Результат вычитания минимумов по столбцам

45
1INF0
30INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(1:5)=0
(3:4)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0 0

Максимальная степень 0 находятся на позициях (1:5)

Удаление из матрицы 1:4

45
100
30INF

Результат удаления из матрицы 1:4

5
3INF

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,4)

5
3INF

Вычитание минимумов по строке

5
3INF

Нахождение минимальных по строкам

Мнимальные по строкам:0

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0

Новая мин граница 190

Результат вычитания минимумов по столбцам

5
3INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:

Конец подсчета штрафов у нулей

Максимумы по строкам:

Граница у несодержащего ребро (1,4):190 у содержащегоINF

Нули на предыдущих этапах:(1:5) (1:4) (4:2) (2:1) (5:3)

Начинаем разделение

45
1INF0
30INF

(1:5)

Поиск циклов

Цикл не найден

Старт обработки множества не включающего в себя ребро (1,5)

45
1INFINF
30INF

Вычитание минимумов по строке

45
1INFINF
30INF

Нахождение минимальных по строкам

Мнимальные по строкам:0 0

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0 0

Новая мин граница 190

Результат вычитания минимумов по столбцам

45
1INFINF
30INF

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(3:4)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (3:4)

Удаление из матрицы 1:5

45
1INF0
30INF

Результат удаления из матрицы 1:5

4
30

Поиск циклов

Цикл не найден

Страт обработки множества включающего в себя ребро (1,5)

4
30

Вычитание минимумов по строке

4
30

Нахождение минимальных по строкам

Мнимальные по строкам:0

Почти новая мин граница 190

Результат вычитания минимумов по строке

Вычитание минимумов по столбцам

Нахождение минимальных по столбцам

Мнимальные по столбцам:0

Новая мин граница 190

Результат вычитания минимумов по столбцам

4
30

Начало подсчета штрафов у нулей

Подсчитанные степени у нулей:
(3:4)=0

Конец подсчета штрафов у нулей

Максимумы по строкам:0

Максимальная степень 0 находятся на позициях (3:4)

Граница у несодержащего ребро (1,5):190 у содержащего190

Нули на предыдущих этапах:(3:4) (1:5) (1:4) (4:2) (2:1) (5:3)

В таблице всего один элемент

4
30

добавили в путь 3:4

Нули на предыдущих этапах:(3:4) (1:5) (1:4) (4:2) (2:1) (5:3)