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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0026488304138184

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

1234567
1INF754313614096
223INF8945299527
37697INF97498150
4683788INF474440
5335280INF524
6044627326INF71
739108439734INF

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

Мнимальные по строкам:13 23 49 37 0 0 4

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

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

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

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

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

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

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6044347326INF70
73565235690INF

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

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

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

Максимумы по строкам:2 3 6 8 2 26 11

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

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

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6044347326INF70
73565235690INF

(6:1)

Поиск циклов

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

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6INF44347326INF70
73565235690INF

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6INF44347326INF70
73565235690INF

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

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

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

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

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

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

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

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

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6INF188470INF44
73565235690INF

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

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

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

Максимумы по строкам:2 6 2 8 2 8 11

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

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

1234567
1INF6220482782
20INF38226723
32748INF480320
431023INF1072
533500INF523
6044347326INF70
73565235690INF

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

234567
16220482782
2INF38226723
348INF480320
4023INF1072
53500INF523
765235690INF

Поиск циклов

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

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

234567
1622048INF82
2INF38226723
348INF480320
4023INF1072
53500INF523
765235690INF

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

234567
1622048INF82
2INF38226723
348INF480320
4023INF1072
53500INF523
765235690INF

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

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

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

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

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

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

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

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

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

234567
1622048INF82
2INF35193690
348INF480320
4023INF1072
53500INF523
765235690INF

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

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

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

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

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

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

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

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

234567
1622048INF82
2INF35193690
348INF480320
4023INF1072
53500INF523
765235690INF

(7:6)

Поиск циклов

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

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

234567
1622048INF82
2INF35193690
348INF480320
4023INF1072
53500INF523
76523569INFINF

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

234567
1622048INF82
2INF35193690
348INF480320
4023INF1072
53500INF523
76523569INFINF

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

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

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

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

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

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

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

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

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

234567
1622048INF82
2INF35193640
348INF480270
4023INF1022
53500INF023
70462963INFINF

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

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

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

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

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

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

234567
1622048INF82
2INF35193690
348INF480320
4023INF1072
53500INF523
765235690INF

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

Поиск циклов

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

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

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

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

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

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

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

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

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

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

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

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

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

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

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

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

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

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

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

(4:2)

Поиск циклов

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

Поиск циклов

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

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

23457
1622048INF
2INF351930
348INF4800
4INF23INF102
53500INF23

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

23457
1622048INF
2INF351930
348INF4800
4INF23INF102
53500INF23

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

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

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

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

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

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

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

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

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

23457
1272048INF
2INF351930
313INF4800
4INF21INF80
5000INF23

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

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

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

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

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

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

23457
162204882
2INF351930
348INF4800
4023INF102
53500INF23

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

3457
1204882
2351930
3INF4800
500INF23

Поиск циклов

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

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

3457
12048INF
235INF30
3INF4800
500INF23

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

3457
12048INF
235INF30
3INF4800
500INF23

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

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

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

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

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

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

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

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

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

3457
12048INF
235INF30
3INF4800
500INF23

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

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

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

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

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

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

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

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

3457
12048INF
235INF30
3INF4800
500INF23

(2:7)

Поиск циклов

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

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

3457
12048INF
235INF3INF
3INF4800
500INF23

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

3457
12048INF
235INF3INF
3INF4800
500INF23

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

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

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

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

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

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

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

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

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

3457
12048INF
232INF0INF
3INF4800
500INF23

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

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

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

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

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

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

3457
12048INF
235INF30
3INF4800
500INF23

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

345
12048
3INF480
500INF

Поиск циклов

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

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

345
12048
3INF480
500INF

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

345
12048
3INF480
500INF

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

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

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

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

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

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

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

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

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

345
12048
3INF480
500INF

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

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

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

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

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

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

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

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

345
12048
3INF480
500INF

(3:5)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

345
12INF48
3INF48INF
500INF

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

345
12INF48
3INF48INF
500INF

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

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

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

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

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

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

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

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

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

345
10INF0
3INF0INF
500INF

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

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

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

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

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

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

345
12048
3INF480
500INF

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

34
120
500

Поиск циклов

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

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

34
12INF
5INF0

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

34
12INF
5INF0

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

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

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

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

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

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

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

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

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

34
10INF
5INF0

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

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

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

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

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

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

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

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

34
10INF
5INF0

(1:3)

Поиск циклов

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

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

34
1INFINF
5INF0

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

34
1INFINF
5INF0

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

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

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

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

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

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

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

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

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

34
1INFINF
5INF0

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

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

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

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

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

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

34
10INF
5INF0

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

4
50

Поиск циклов

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

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

4
50

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

4
50

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

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

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

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

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

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

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

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

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

4
50

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

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

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

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

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

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

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

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

4
50

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

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