Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
B
C
D
E
F
A
2
4
4
B
2
4
1
C
4
2
1
D
2
2
E
4
1
F
4
1
2
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).
A
B
C
D
E
F
A
2
4
4
B
2
4
1
C
4
2
1
D
2
2
E
4
1
F
4
1
2
Определите длину кратчайшего пути между пунктами A и D (при условии, что передвигаться можно только по построенным дорогам).
💡 Пошаговый разбор и решение:
Найдём все варианты маршрутов из A в D и выберем самый короткий.
В пункт D можно попасть из пунктов С и F.
В пункты F можно попасть из пунктов А и B.
В пункт С можно попасть из пунктов B и Е.
В пункты E и В можно попасть из пункта А.
A-B-C-D. Длина маршрута 2 + 4 + 2 = 8.
A-E-C-D. Длина маршрута 4 + 1 + 2 = 7.
A-F-D. Длина маршрута 4 + 2 = 6.
A-B-F-D. Длина маршрута 2 + 1 + 2 = 5.
Видно, что кратчайший путь равен 5.
В пункт D можно попасть из пунктов С и F.
В пункты F можно попасть из пунктов А и B.
В пункт С можно попасть из пунктов B и Е.
В пункты E и В можно попасть из пункта А.
A-B-C-D. Длина маршрута 2 + 4 + 2 = 8.
A-E-C-D. Длина маршрута 4 + 1 + 2 = 7.
A-F-D. Длина маршрута 4 + 2 = 6.
A-B-F-D. Длина маршрута 2 + 1 + 2 = 5.
Видно, что кратчайший путь равен 5.
Правильный ответ:
5
📚 Похожие разобранные задания по предмету:
ID 31845 • Задание №12
Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов: X, Y, Z.
Дан фрагмент та...
ID 32283 • Задание №14
Значение арифметического выражения
7 · 512120 − 6 · 64100 + 8210 − 255
записали в системе счисления с основа...
🔗 Другие задания линии №1 по предмету Информатика:
ID 29120
На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся све...
ID 29121
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличи...
ID 29122
На рисунке схема дорог изображена в виде графа, в таблице звёздочкой обозначено наличие дороги ...
ID 29123
На рисунке слева изображена схема дорог Н-ского района, в таблице звёздочкой обозначено наличи...
ID 29124
На рисунке слева изображена схема дорог N-ского района. В таблице звёздочкой обозначено наличи...