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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.0023458003997803

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

1234567
1INF981835992180
288INF9763251431
3685INF87915985
4954745INF3654
568648198INF9477
69462951499INF26
7904616215292INF

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

Мнимальные по строкам:18 14 5 4 64 14 16

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

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

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

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

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

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

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

1234567
1INF8001770362
270INF83490017
3590INF82755480
4874341INF2110
5001734INF3013
6764881074INF12
77030052576INF

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

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

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

Максимумы по строкам:3 21 54 13 59 17 5

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

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

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

1234567
1INF8001770362
270INF83490017
3590INF82755480
4874341INF2110
5001734INF3013
6764881074INF12
77030052576INF

(5:1)

Поиск циклов

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

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

1234567
1INF8001770362
270INF83490017
3590INF82755480
4874341INF2110
5INF01734INF3013
6764881074INF12
77030052576INF

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

1234567
1INF8001770362
270INF83490017
3590INF82755480
4874341INF2110
5INF01734INF3013
6764881074INF12
77030052576INF

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

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

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

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

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

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

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

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

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

1234567
1INF8001770362
211INF83490017
300INF82755480
4284341INF2110
5INF01734INF3013
6174881074INF12
71130052576INF

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

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

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

Максимумы по строкам:3 21 11 13 13 17 5

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

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

1234567
1INF8001770362
270INF83490017
3590INF82755480
4874341INF2110
5001734INF3013
6764881074INF12
77030052576INF

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

234567
18001770362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

Поиск циклов

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

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

234567
180017INF362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

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

234567
180017INF362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

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

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

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

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

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

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

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

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

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

234567
180017INF362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

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

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

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

Максимумы по строкам:3 21 84 13 17 5

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

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

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

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

234567
180017INF362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

(3:2)

Поиск циклов

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

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

234567
180017INF362
2INF83490017
3INFINF82755480
44341INF2110
64881074INF12
730052576INF

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

234567
180017INF362
2INF83490017
3INFINF82755480
44341INF2110
64881074INF12
730052576INF

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

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

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

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

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

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

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

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

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

234567
150017INF362
2INF83490017
3INFINF2821026
41341INF2110
61881074INF12
70052576INF

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

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

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

Максимумы по строкам:3 21 21 13 17 13

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

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

234567
180017INF362
2INF83490017
30INF82755480
44341INF2110
64881074INF12
730052576INF

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

34567
1017INF362
283490017
441INF2110
681074INF12
7052576INF

Поиск циклов

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

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

34567
1017INF362
2INF490017
441INF2110
681074INF12
7052576INF

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

34567
1017INF362
2INF490017
441INF2110
681074INF12
7052576INF

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

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

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

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

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

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

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

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

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

34567
1017INF362
2INF490017
441INF2110
681074INF12
7052576INF

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

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

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

Максимумы по строкам:3 21 13 17 5

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

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

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

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

34567
1017INF362
2INF490017
441INF2110
681074INF12
7052576INF

(2:5)

Поиск циклов

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

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

34567
1017INF362
2INF49INF017
441INF2110
681074INF12
7052576INF

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

34567
1017INF362
2INF49INF017
441INF2110
681074INF12
7052576INF

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

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

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

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

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

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

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

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

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

34567
1017INF362
2INF49INF017
441INF010
681053INF12
705476INF

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

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

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

Максимумы по строкам:3 18 12 17 4

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

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

34567
1017INF362
2INF490017
441INF2110
681074INF12
7052576INF

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

3467
1017362
441INF10
6810INF12
70576INF

Поиск циклов

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

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

3467
1017362
441INF10
6810INF12
70576INF

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

3467
1017362
441INF10
6810INF12
70576INF

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

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

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

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

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

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

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

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

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

3467
1017262
441INF00
6810INF12
70575INF

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

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

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

Максимумы по строкам:2 12 17 5

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

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

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

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

3467
1017262
441INF00
6810INF12
70575INF

(6:4)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

3467
1INF17262
441INF00
681INFINF12
70575INF

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

3467
1INF17262
441INF00
681INFINF12
70575INF

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

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

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

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

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

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

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

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

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

3467
1INF10060
441INF00
669INFINF0
70075INF

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

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

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

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

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

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

3467
1017262
441INF00
6810INF12
70575INF

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

367
10262
44100
7075INF

Поиск циклов

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

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

367
1INF262
441INF0
7075INF

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

367
1INF262
441INF0
7075INF

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

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

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

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

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

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

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

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

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

367
1INF060
441INF0
7075INF

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

Подсчитанные степени у нулей:
(1:6)=135
(4:7)=101
(7:3)=116

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

Максимумы по строкам:135 101 116

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

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

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

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

367
1INF060
441INF0
7075INF

(1:6)

Поиск циклов

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

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

367
1INFINF60
441INF0
7075INF

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

367
1INFINF60
441INF0
7075INF

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

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

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

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

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

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

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

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

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

367
1INFINF0
441INF0
700INF

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

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

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

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

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

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

367
1INF060
441INF0
7075INF

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

37
4410
70INF

Поиск циклов

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

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

37
4410
70INF

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

37
4410
70INF

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

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

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

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

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

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

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

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

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

37
4410
70INF

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

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

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

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

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

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

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

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

37
4410
70INF

(4:7)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

37
4INFINF
70INF

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

37
4INFINF
70INF

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

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

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

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

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

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

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

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

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

37
4INFINF
70INF

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

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

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

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

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

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

37
4410
70INF

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

3
70

Поиск циклов

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

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

3
70

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

3
70

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

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

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

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

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

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

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

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

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

3
70

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

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

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

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

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

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

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

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

3
70

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

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