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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0027620792388916

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

1234567
1INF55636992553
240INF9150124915
32262INF85766688
457315INF16155
5435353INF1871
6292815659INF5
7504897274848INF

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

Мнимальные по строкам:5 12 22 1 3 2 27

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

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

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

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

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

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

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

1234567
1INF04731942045
228INF75380370
3040INF63544463
456300INF15051
5104650INF1565
6090755457INF0
723216602121INF

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

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

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

Максимумы по строкам:20 15 40 46 1 0 52

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

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

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

1234567
1INF04731942045
228INF75380370
3040INF63544463
456300INF15051
5104650INF1565
6090755457INF0
723216602121INF

(7:4)

Поиск циклов

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

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

1234567
1INF04731942045
228INF75380370
3040INF63544463
456300INF15051
5104650INF1565
6090755457INF0
7232166INF2121INF

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

1234567
1INF04731942045
228INF75380370
3040INF63544463
456300INF15051
5104650INF1565
6090755457INF0
7232166INF2121INF

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

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

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

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

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

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

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

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

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

1234567
1INF0470942045
228INF7570370
3040INF32544463
456300INF15051
5104619INF1565
6090752357INF0
72045INF00INF

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

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

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

Максимумы по строкам:7 0 32 45 1 0 0

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

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

1234567
1INF04731942045
228INF75380370
3040INF63544463
456300INF15051
5104650INF1565
6090755457INF0
723216602121INF

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

123567
1INF047942045
228INF750370
3040INF544463
45630015051
51046INF1565
60907557INF0

Поиск циклов

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

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

123567
1INF047942045
228INF750370
3040INF544463
456300150INF
51046INF1565
60907557INF0

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

123567
1INF047942045
228INF750370
3040INF544463
456300150INF
51046INF1565
60907557INF0

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

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

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

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

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

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

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

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

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

123567
1INF047942045
228INF750370
3040INF544463
456300150INF
51046INF1565
60907557INF0

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

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

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

Максимумы по строкам:20 15 40 46 1 0

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

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

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

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

123567
1INF047942045
228INF750370
3040INF544463
456300150INF
51046INF1565
60907557INF0

(4:3)

Поиск циклов

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

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

123567
1INF047942045
228INF750370
3040INF544463
45630INF150INF
51046INF1565
60907557INF0

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

123567
1INF047942045
228INF750370
3040INF544463
45630INF150INF
51046INF1565
60907557INF0

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

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

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

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

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

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

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

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

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

123567
1INF01942045
228INF290370
3040INF544463
45630INF150INF
5100INF1565
60902957INF0

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

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

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

Максимумы по строкам:1 15 40 30 1 0

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

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

123567
1INF047942045
228INF750370
3040INF544463
456300150INF
51046INF1565
60907557INF0

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

12567
1INF0942045
228INF0370
3040544463
510INF1565
609057INF0

Поиск циклов

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

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

12567
1INF0942045
228INF0370
3040544463
510INF1565
609057INF0

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

12567
1INF0942045
228INF0370
3040544463
510INF1565
609057INF0

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

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

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

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

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

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

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

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

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

12567
1INF094545
228INF0220
3040542963
510INF065
609057INF0

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

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

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

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

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

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

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

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

12567
1INF094545
228INF0220
3040542963
510INF065
609057INF0

(2:5)

Поиск циклов

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

Поиск циклов

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

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

12567
1INF094545
228INFINF220
30405429INF
510INF065
609057INF0

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

12567
1INF094545
228INFINF220
30405429INF
510INF065
609057INF0

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

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

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

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

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

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

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

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

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

12567
1INF040545
228INFINF220
3040029INF
510INF065
60903INF0

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

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

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

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

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

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

12567
1INF094545
228INF0220
3040542963
510INF065
609057INF0

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

1267
1INF0545
30402963
510065
6090INF0

Поиск циклов

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

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

1267
1INF0545
304029INF
51INF065
6090INF0

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

1267
1INF0545
304029INF
51INF065
6090INF0

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

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

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

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

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

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

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

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

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

1267
1INF0545
304029INF
51INF065
6090INF0

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

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

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

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

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

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

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

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

1267
1INF0545
304029INF
51INF065
6090INF0

(1:2)

Поиск циклов

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

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

1267
1INFINF545
304029INF
51INF065
6090INF0

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

1267
1INFINF545
304029INF
51INF065
6090INF0

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

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

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

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

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

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

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

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

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

1267
1INFINF040
30029INF
51INF065
6050INF0

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

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

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

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

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

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

1267
1INF0545
304029INF
51INF065
6090INF0

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

167
3029INF
51065
60INF0

Поиск циклов

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

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

167
3029INF
51065
60INF0

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

167
3029INF
51065
60INF0

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

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

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

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

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

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

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

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

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

167
3029INF
51065
60INF0

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

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

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

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

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

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

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

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

167
3029INF
51065
60INF0

(6:7)

Поиск циклов

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

Поиск циклов

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

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

167
3029INF
5INF065
60INFINF

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

167
3029INF
5INF065
60INFINF

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

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

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

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

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

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

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

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

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

167
3029INF
5INF00
60INFINF

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

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

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

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

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

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

167
3029INF
51065
60INF0

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

16
3029
510

Поиск циклов

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

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

16
3029
5INF0

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

16
3029
5INF0

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

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

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

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

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

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

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

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

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

16
3029
5INF0

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

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

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

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

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

Граница у несодержащего ребро (6,7):159 у содержащего94

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

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

16
3029
5INF0

(3:1)

Поиск циклов

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

Поиск циклов

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

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

16
3INFINF
5INF0

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

16
3INFINF
5INF0

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

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

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

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

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

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

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

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

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

16
3INFINF
5INF0

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

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

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

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

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

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

16
3029
5INF0

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

6
50

Поиск циклов

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

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

6
50

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

6
50

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

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

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

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

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

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

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

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

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

6
50

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

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

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

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

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

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

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

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

6
50

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

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