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

Источник

Источник

Источник

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

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

1234567
1
2
3
4
5
6
7

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

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

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

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

Время:0.023206949234009

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

1234567
1INF64036398094
24INF613982626
3814INF97979318
4128417INF245665
569256597INF100
6183203522INF67
7125623186844INF

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

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

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

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

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

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

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

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

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

1234567
1INF02930216488
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

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

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

Максимумы по строкам:21 7 14 9 14 9 6

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

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

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

1234567
1INF02930216488
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

(1:2)

Поиск циклов

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

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

1234567
1INFINF2930216488
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

1234567
1INFINF2930216488
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

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

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

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

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

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

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

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

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

1234567
1INFINF8904367
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

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

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

Максимумы по строкам:8 7 39 6 14 9 6

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

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

1234567
1INF02930216488
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

134567
21530831323
377INF93817914
400INF03453
5696097INF00
6014349INF66
70664422INF

Поиск циклов

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

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

134567
2INF530831323
377INF93817914
400INF03453
5696097INF00
6014349INF66
70664422INF

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

134567
2INF530831323
377INF93817914
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

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

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

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

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

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

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

134567
2INF530831323
363INF7967650
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

Максимумы по строкам:19 63 9 13 9 6

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

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

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

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

134567
2INF530831323
363INF7967650
400INF03453
5696097INF00
6014349INF66
70664422INF

(3:7)

Поиск циклов

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

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

134567
2INF530831323
363INF796765INF
400INF03453
5696097INF00
6014349INF66
70664422INF

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

134567
2INF530831323
363INF796765INF
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

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

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

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

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

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

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

134567
2INF530831323
30INF1642INF
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

Максимумы по строкам:19 2 6 23 9 6

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

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

134567
2INF530831323
363INF7967650
400INF03453
5696097INF00
6014349INF66
70664422INF

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70664422

Поиск циклов

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

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70INF64422

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70INF64422

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

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

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

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

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

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

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

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

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70INF64422

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

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

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

Максимумы по строкам:19 14 73 9 6

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

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

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

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70INF64422

(5:6)

Поиск циклов

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

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

13456
2INF5308313
400INF034
5696097INFINF
6014349INF
70INF64422

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

13456
2INF5308313
400INF034
5696097INFINF
6014349INF
70INF64422

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

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

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

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

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

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

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

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

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

13456
2INF530830
400INF021
59037INFINF
6014349INF
70INF6449

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

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

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

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

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

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

13456
2INF5308313
400INF034
5696097INF0
6014349INF
70INF64422

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

1345
2INF53083
400INF0
6014349
70INF644

Поиск циклов

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

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

1345
2INF53083
400INF0
601434INF
70INF644

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

1345
2INF53083
400INF0
601434INF
70INF644

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

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

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

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

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

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

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

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

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

1345
2INF53083
400INF0
601434INF
70INF644

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

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

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

Максимумы по строкам:59 44 14 6

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

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

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

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

1345
2INF53083
400INF0
601434INF
70INF644

(2:4)

Поиск циклов

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

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

1345
2INF53INF83
400INF0
601434INF
70INF644

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

1345
2INF53INF83
400INF0
601434INF
70INF644

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

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

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

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

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

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

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

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

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

1345
2INF0INF30
400INF0
601428INF
70INF044

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

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

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

Максимумы по строкам:30 30 14 28

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

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

1345
2INF53083
400INF0
601434INF
70INF644

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

135
4000
6014INF
70INF44

Поиск циклов

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

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

135
4000
6014INF
70INF44

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

135
4000
6014INF
70INF44

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

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

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

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

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

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

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

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

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

135
4000
6014INF
70INF44

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

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

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

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

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

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

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

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

135
4000
6014INF
70INF44

(4:5)

Поиск циклов

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

Поиск циклов

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

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

135
4INF0INF
6014INF
70INF44

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

135
4INF0INF
6014INF
70INF44

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

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

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

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

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

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

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

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

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

135
4INF0INF
6014INF
70INF0

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

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

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

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

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

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

135
4000
6014INF
70INF44

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

13
6014
70INF

Поиск циклов

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

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

13
6014
70INF

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

13
6014
70INF

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

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

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

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

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

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

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

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

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

13
600
70INF

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

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

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

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

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

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

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

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

1234567
1INFINF8904367
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

(3:2)

Поиск циклов

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

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

1234567
1INFINF8904367
21INF530831323
377INFINF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

1234567
1INFINF8904367
21INF530831323
377INFINF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

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

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

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

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

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

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

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

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

1234567
1INFINF8904367
21INF530831323
363INFINF7967650
40470INF03453
56906097INF00
605714349INF66
7019664422INF

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

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

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

Максимумы по строкам:8 7 63 6 19 9 6

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

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

1234567
1INFINF8904367
21INF530831323
3770INF93817914
40720INF03453
569256097INF00
608214349INF66
7044664422INF

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

134567
1INF8904367
21530831323
400INF03453
5696097INF00
6014349INF66
70664422INF

Поиск циклов

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

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF00
6014349INF66
70664422INF

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

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

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

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

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

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

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF00
6014349INF66
70664422INF

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

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

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

Максимумы по строкам:8 7 6 23 9 6

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

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

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

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF00
6014349INF66
70664422INF

(5:7)

Поиск циклов

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

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF0INF
6014349INF66
70664422INF

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF0INF
6014349INF66
70664422INF

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

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

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

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

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

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

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

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

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

134567
1INF8904344
21INF083130
400INF03430
5696097INF0INF
6014349INF43
70664422INF

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

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

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

Максимумы по строкам:8 30 6 73 9 6

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

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

134567
1INF8904367
21INF0831323
400INF03453
5696097INF00
6014349INF66
70664422INF

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

13456
1INF89043
21INF08313
400INF034
6014349INF
70664422

Поиск циклов

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

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

13456
1INF89043
21INF08313
400INF034
6014349INF
7066INF22

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

13456
1INF89043
21INF08313
400INF034
6014349INF
7066INF22

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

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

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

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

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

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

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

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

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

13456
1INF89030
21INF0830
400INF021
6014349INF
7066INF9

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

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

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

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

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

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

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

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

13
600
70INF

(6:1)

Поиск циклов

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

Поиск циклов

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

Поиск циклов

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

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

13
6INF0
70INF

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

13
6INF0
70INF

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

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

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

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

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

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

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

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

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

13
6INF0
70INF

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

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

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

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

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

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

13
600
70INF

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

3
7INF

Поиск циклов

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

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

3
7INF

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

3
7INF

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

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

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

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

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

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

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

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

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

3
7INF

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

Подсчитанные степени у нулей:

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

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

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

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

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

13
6INF0
70INF

(6:3)

Поиск циклов

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

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

13
6INFINF
70INF

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

13
6INFINF
70INF

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

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

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

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

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

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

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

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

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

13
6INFINF
70INF

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

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

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

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

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

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

13
6INF0
70INF

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

1
70

Поиск циклов

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

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

1
70

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

1
70

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

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

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

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

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

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

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

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

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

1
70

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

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

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

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

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

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

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

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

1
70

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

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