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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0024418830871582

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

1234567
1INF6917915346
210INF5784683953
32188INF543291
479758INF745415
511999174INF299
66576226653INF33
7914429911411INF

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

Мнимальные по строкам:3 10 1 8 9 22 11

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

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

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

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

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

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

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

1234567
1INF0883210043
20INF4730562943
32084INF90280
471640INF64467
52878221INF200
643510029INF11
78030183610INF

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

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

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

Максимумы по строкам:30 31 1 7 2 9 1

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

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

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

1234567
1INF0883210043
20INF4730562943
32084INF90280
471640INF64467
52878221INF200
643510029INF11
78030183610INF

(2:1)

Поиск циклов

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

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

1234567
1INF0883210043
2INFINF4730562943
32084INF90280
471640INF64467
52878221INF200
643510029INF11
78030183610INF

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

1234567
1INF0883210043
2INFINF4730562943
32084INF90280
471640INF64467
52878221INF200
643510029INF11
78030183610INF

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

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

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

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

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

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

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

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

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

1234567
1INF0883210043
2INFINF18127014
31884INF90280
469640INF64467
50878221INF200
641510029INF11
77830183610INF

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

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

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

Максимумы по строкам:30 1 1 7 18 1 1

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

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

1234567
1INF0883210043
20INF4730562943
32084INF90280
471640INF64467
52878221INF200
643510029INF11
78030183610INF

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

234567
10883210043
384INF90280
4640INF64467
5878221INF200
6510029INF11
730183610INF

Поиск циклов

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

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

234567
1INF883210043
384INF90280
4640INF64467
5878221INF200
6510029INF11
730183610INF

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

234567
1INF883210043
384INF90280
4640INF64467
5878221INF200
6510029INF11
730183610INF

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

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

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

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

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

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

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

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

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

234567
1INF883210043
354INF90280
4340INF64467
5578221INF200
6210029INF11
70183610INF

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

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

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

Максимумы по строкам:10 1 7 20 9 21

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

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

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

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

234567
1INF883210043
354INF90280
4340INF64467
5578221INF200
6210029INF11
70183610INF

(7:2)

Поиск циклов

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

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

234567
1INF883210043
354INF90280
4340INF64467
5578221INF200
6210029INF11
7INF183610INF

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

234567
1INF883210043
354INF90280
4340INF64467
5578221INF200
6210029INF11
7INF183610INF

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

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

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

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

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

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

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

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

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

234567
1INF883210043
333INF90280
4130INF64467
5368221INF200
600029INF11
7INF183610INF

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

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

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

Максимумы по строкам:10 1 7 20 13 1

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

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

234567
1INF883210043
354INF90280
4340INF64467
5578221INF200
6210029INF11
70183610INF

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

Поиск циклов

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

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

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

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

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

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

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

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

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

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

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

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

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

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

Максимумы по строкам:30 10 7 20 9

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

Граница у несодержащего ребро (7,2):164 у содержащего143

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

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

(1:6)

Поиск циклов

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

Поиск циклов

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

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

34567
1883210INFINF
3INF90280
40INF64467
58221INF200
60029INF11

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

34567
1883210INFINF
3INF90280
40INF64467
58221INF200
60029INF11

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

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

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

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

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

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

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

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

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

34567
178220INFINF
3INF9080
40INF64267
58221INF00
60029INF11

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

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

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

Максимумы по строкам:22 0 7 8 9

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

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

34567
1883210043
3INF90280
40INF64467
58221INF200
60029INF11

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

3457
3INF900
40INF647
58221INF0
6002911

Поиск циклов

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

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

3457
3INF900
40INF647
58221INF0
6002911

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

3457
3INF900
40INF647
58221INF0
6002911

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

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

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

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

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

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

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

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

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

3457
3INF900
40INF647
58221INF0
6002911

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

Подсчитанные степени у нулей:
(3:5)=29
(3:7)=0
(4:3)=7
(5:7)=21
(6:3)=0
(6:4)=9

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

Максимумы по строкам:29 7 21 9

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

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

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

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

3457
3INF900
40INF647
58221INF0
6002911

(3:5)

Поиск циклов

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

Поиск циклов

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

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

3457
3INF9INF0
40INF647
58221INF0
60029INF

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

3457
3INF9INF0
40INF647
58221INF0
60029INF

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

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

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

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

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

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

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

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

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

3457
3INF9INF0
40INF357
58221INF0
6000INF

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

Подсчитанные степени у нулей:
(3:7)=9
(4:3)=7
(5:7)=21
(6:3)=0
(6:4)=9
(6:5)=35

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

Максимумы по строкам:9 7 21 35

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

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

3457
3INF900
40INF647
58221INF0
6002911

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

347
40INF7
582210
60011

Поиск циклов

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

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

347
40INF7
5INF210
600INF

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

347
40INF7
5INF210
600INF

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

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

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

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

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

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

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

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

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

347
40INF7
5INF210
600INF

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

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

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

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

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

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

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

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

347
40INF7
5INF210
600INF

(5:7)

Поиск циклов

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

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

347
40INF7
5INF21INF
600INF

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

347
40INF7
5INF21INF
600INF

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

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

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

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

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

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

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

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

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

347
40INF0
5INF0INF
600INF

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

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

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

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

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

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

347
40INF7
5INF210
600INF

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

34
40INF
600

Поиск циклов

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

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

34
40INF
600

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

34
40INF
600

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

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

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

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

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

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

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

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

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

34
40INF
600

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

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

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

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

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

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

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

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

34
40INF
600

(4:3)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

34
4INFINF
6INF0

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

34
4INFINF
6INF0

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

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

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

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

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

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

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

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

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

34
4INFINF
6INF0

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

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

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

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

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

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

34
40INF
600

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

4
60

Поиск циклов

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

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

4
60

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

4
60

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

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

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

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

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

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

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

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

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

4
60

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

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

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

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

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

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

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

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

4
60

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

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