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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0032010078430176

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

1234567
1INF751895792998
25INF813005967
39018INF65898119
469186INF32667
559249420INF561
67616811643INF34
7397927202297INF

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

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

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

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

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

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

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

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

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

1234567
1INF57077611179
20INF813005966
3670INF4771630
458120INF26060
549198915INF055
655065027INF17
7145970277INF

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

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

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

Максимумы по строкам:11 14 17 0 15 0 2

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

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

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

1234567
1INF57077611179
20INF813005966
3670INF4771630
458120INF26060
549198915INF055
655065027INF17
7145970277INF

(3:7)

Поиск циклов

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

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

1234567
1INF57077611179
20INF813005966
3670INF477163INF
458120INF26060
549198915INF055
655065027INF17
7145970277INF

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

1234567
1INF57077611179
20INF813005966
3670INF477163INF
458120INF26060
549198915INF055
655065027INF17
7145970277INF

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

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

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

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

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

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

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

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

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

1234567
1INF57077611162
20INF813005949
3670INF477163INF
458120INF26043
549198915INF038
655065027INF0
7145970277INF

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

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

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

Максимумы по строкам:11 14 47 0 15 38 2

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

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

1234567
1INF57077611179
20INF813005966
3670INF4771630
458120INF26060
549198915INF055
655065027INF17
7145970277INF

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
7145970277

Поиск циклов

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

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
71459INF0277

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
71459INF0277

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

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

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

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

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

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

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

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

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
71459INF0277

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

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

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

Максимумы по строкам:11 14 0 15 12 2

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

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

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

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
71459INF0277

(5:6)

Поиск циклов

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

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INFINF
655065027INF
71459INF0277

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INFINF
655065027INF
71459INF0277

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

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

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

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

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

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

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

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

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

123456
1INF570776111
20INF8130059
458120INF260
5344740INFINF
655065027INF
71459INF0277

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

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

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

Максимумы по строкам:11 14 11 4 4 2

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

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

123456
1INF570776111
20INF8130059
458120INF260
549198915INF0
655065027INF
71459INF0277

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

12345
1INF5707761
20INF81300
458120INF26
655065027
71459INF02

Поиск циклов

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

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

12345
1INF5707761
20INF81300
458120INF26
6550650INF
71459INF02

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

12345
1INF5707761
20INF81300
458120INF26
6550650INF
71459INF02

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

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

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

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

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

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

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

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

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

12345
1INF5707761
20INF81300
458120INF26
6550650INF
71459INF02

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

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

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

Максимумы по строкам:57 14 12 12 2

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

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

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

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

12345
1INF5707761
20INF81300
458120INF26
6550650INF
71459INF02

(1:3)

Поиск циклов

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

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

12345
1INF57INF7761
20INF81300
458120INF26
6550650INF
71459INF02

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

12345
1INF57INF7761
20INF81300
458120INF26
6550650INF
71459INF02

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

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

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

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

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

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

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

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

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

12345
1INF0INF204
20INF81300
458120INF26
6550650INF
71459INF02

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

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

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

Максимумы по строкам:4 14 77 0 2

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

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

12345
1INF5707761
20INF81300
458120INF26
6550650INF
71459INF02

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

1245
20INF300
45812INF26
65500INF
7145902

Поиск циклов

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

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

1245
20INF300
45812INF26
65500INF
7145902

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

1245
20INF300
45812INF26
65500INF
7145902

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

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

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

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

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

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

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

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

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

1245
20INF300
4460INF14
65500INF
7145902

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

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

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

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

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

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

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

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

1245
20INF300
4460INF14
65500INF
7145902

(2:1)

Поиск циклов

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

Поиск циклов

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

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

1245
2INFINF300
4460INF14
65500INF
7INF5902

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

1245
2INFINF300
4460INF14
65500INF
7INF5902

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

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

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

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

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

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

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

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

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

1245
2INFINF300
400INF14
6900INF
7INF5902

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

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

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

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

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

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

1245
20INF300
4460INF14
65500INF
7145902

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

245
40INF14
600INF
75902

Поиск циклов

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

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

245
40INF14
600INF
75902

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

245
40INF14
600INF
75902

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

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

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

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

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

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

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

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

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

245
40INF12
600INF
75900

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

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

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

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

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

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

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

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

245
40INF12
600INF
75900

(4:2)

Поиск циклов

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

Поиск циклов

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

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

245
4INFINF12
600INF
7INF00

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

245
4INFINF12
600INF
7INF00

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

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

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

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

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

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

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

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

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

245
4INFINF0
600INF
7INF00

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

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

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

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

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

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

245
40INF12
600INF
75900

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

45
60INF
700

Поиск циклов

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

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

45
60INF
700

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

45
60INF
700

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

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

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

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

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

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

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

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

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

45
60INF
700

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

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

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

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

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

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

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

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

45
60INF
700

(6:4)

Поиск циклов

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

Поиск циклов

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

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

45
6INFINF
7INF0

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

45
6INFINF
7INF0

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

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

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

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

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

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

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

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

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

45
6INFINF
7INF0

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

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

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

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

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

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

45
60INF
700

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

5
70

Поиск циклов

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

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

5
70

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

5
70

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

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

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

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

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

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

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

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

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

5
70

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

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

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

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

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

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

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

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

5
70

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

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