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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0028500556945801

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

1234567
1INF484727554458
249INF851438778
35137INF88637141
4621756INF26846
55252877INF8548
61084745259INF98
7422114432491INF

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

Мнимальные по строкам:27 3 37 6 8 10 14

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

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

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

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

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

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

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

1234567
1INF2120028031
246INF821106775
3140INF5126174
4561150INF20610
54444069INF6040
6074644249INF88
72870291060INF

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

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

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

Максимумы по строкам:17 21 11 15 40 56 7

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

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

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

1234567
1INF2120028031
246INF821106775
3140INF5126174
4561150INF20610
54444069INF6040
6074644249INF88
72870291060INF

(6:1)

Поиск циклов

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

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

1234567
1INF2120028031
246INF821106775
3140INF5126174
4561150INF20610
54444069INF6040
6INF74644249INF88
72870291060INF

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

1234567
1INF2120028031
246INF821106775
3140INF5126174
4561150INF20610
54444069INF6040
6INF74644249INF88
72870291060INF

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

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

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

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

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

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

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

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

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

1234567
1INF2120028031
232INF821106775
300INF5126174
4421150INF20610
53044069INF6040
6INF322207INF46
71470291060INF

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

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

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

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

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

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

1234567
1INF2120028031
246INF821106775
3140INF5126174
4561150INF20610
54444069INF6040
6074644249INF88
72870291060INF

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

234567
12120028031
2INF821106775
30INF5126174
41150INF20610
544069INF6040
770291060INF

Поиск циклов

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

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

234567
12120028INF31
2INF821106775
30INF5126174
41150INF20610
544069INF6040
770291060INF

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

234567
12120028INF31
2INF821106775
30INF5126174
41150INF20610
544069INF6040
770291060INF

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

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

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

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

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

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

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

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

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

234567
12120028INF31
2INF821105075
30INF512604
41150INF20440
544069INF4340
770291043INF

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

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

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

Максимумы по строкам:31 21 43 15 40 7

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

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

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

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

234567
12120028INF31
2INF821105075
30INF512604
41150INF20440
544069INF4340
770291043INF

(3:6)

Поиск циклов

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

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

234567
12120028INF31
2INF821105075
30INF5126INF4
41150INF20440
544069INF4340
770291043INF

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

234567
12120028INF31
2INF821105075
30INF5126INF4
41150INF20440
544069INF4340
770291043INF

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

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

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

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

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

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

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

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

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

234567
12120028INF31
2INF82110775
30INF5126INF4
41150INF2010
544069INF040
77029100INF

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

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

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

Максимумы по строкам:31 17 11 5 0 0

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

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

234567
12120028INF31
2INF821105075
30INF512604
41150INF20440
544069INF4340
770291043INF

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

23457
1212002831
2INF8211075
41150INF200
544069INF40
7702910INF

Поиск циклов

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

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

23457
1212002831
2INF8211075
41150INF200
544069INF40
7702910INF

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

23457
1212002831
2INF8211075
41150INF200
544069INF40
7702910INF

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

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

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

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

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

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

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

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

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

23457
1142002831
2INF8211075
4450INF200
537069INF40
7002910INF

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

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

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

Максимумы по строкам:25 21 35 37 4

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

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

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

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

23457
1142002831
2INF8211075
4450INF200
537069INF40
7002910INF

(5:3)

Поиск циклов

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

Поиск циклов

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

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

23457
114INF02831
2INF8211075
4450INF200
537INF69INF40
7002910INF

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

23457
114INF02831
2INF8211075
4450INF200
537INF69INF40
7002910INF

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

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

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

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

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

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

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

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

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

23457
114INF02831
2INF8211075
4450INF200
50INF32INF3
7002910INF

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

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

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

Максимумы по строкам:25 21 7 3 50

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

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

23457
1142002831
2INF8211075
4450INF200
537069INF40
7002910INF

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

2457
11402831
2INF11075
44INF200
702910INF

Поиск циклов

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

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

2457
11402831
2INF11075
44INF200
702910INF

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

2457
11402831
2INF11075
44INF200
702910INF

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

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

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

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

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

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

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

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

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

2457
11402831
2INF11075
44INF200
702910INF

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

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

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

Максимумы по строкам:25 21 35 14

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

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

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

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

2457
11402831
2INF11075
44INF200
702910INF

(4:7)

Поиск циклов

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

Поиск циклов

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

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

2457
1140INF31
2INF11075
44INF20INF
702910INF

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

2457
1140INF31
2INF11075
44INF20INF
702910INF

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

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

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

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

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

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

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

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

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

2457
1140INF0
2INF11044
40INF16INF
702910INF

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

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

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

Максимумы по строкам:44 21 16 10

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

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

2457
11402831
2INF11075
44INF200
702910INF

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

245
114028
2INF110
702910

Поиск циклов

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

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

245
1140INF
2INF110
70INF10

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

245
1140INF
2INF110
70INF10

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

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

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

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

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

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

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

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

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

245
1140INF
2INF110
70INF10

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

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

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

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

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

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

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

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

245
1140INF
2INF110
70INF10

(1:4)

Поиск циклов

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

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

245
114INFINF
2INF110
70INF10

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

245
114INFINF
2INF110
70INF10

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

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

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

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

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

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

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

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

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

245
10INFINF
2INF00
70INF10

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

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

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

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

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

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

245
1140INF
2INF110
70INF10

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

25
2INF0
7010

Поиск циклов

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

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

25
2INF0
7010

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

25
2INF0
7010

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

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

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

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

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

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

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

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

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

25
2INF0
7010

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

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

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

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

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

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

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

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

25
2INF0
7010

(2:5)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

25
2INFINF
70INF

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

25
2INFINF
70INF

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

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

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

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

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

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

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

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

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

25
2INFINF
70INF

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

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

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

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

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

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

25
2INF0
7010

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

2
70

Поиск циклов

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

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

2
70

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

2
70

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

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

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

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

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

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

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

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

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

2
70

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

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

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

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

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

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

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

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

2
70

добавили в путь 7:2

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