ГДЗ по информатике 9 класс Босова, номер §2.4 № 6

§. № Сравнение стоимости маршрутов

Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость перевозок между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Стоимость перевозок по маршруту складывается из стоимостей перевозок между соседними станциями. Перевозки между населёнными пунктами A, B, C, D, E осуществляют три компании, представившие стоимость своих услуг в табличной форме. Какая компания обеспечивает минимальную стоимость перевозок из A в B?

	A	B	C	D	E
A			3	1
B			4		2
C	3	4			2
D	1
E		2	2

	A	B	C	D	E
A			3	1	1
B			4
C	3	4			2
D	1
E	1		2

	A	B	C	D	E
A			3	1	4
B			4		2
C	3	4			2
D	1
E	4	2	2

Решение

Пустая клетка весовой матрицы означает отсутствие прямого переезда. Поэтому для каждой компании рассматриваем только цепочки соединённых станций и складываем стоимости соседних участков. Пункт D соединён только с A, так что маршрут A–D не может привести в B без возвращения в A.

У компании возможны маршруты A–C–B и A–C–E–B. Первый стоит . Второй стоит , затем . Значит, минимальная стоимость компании — .

У компании есть маршруты A–C–B и A–E–C–B. Первый стоит . Для второго получаем , . Из E напрямую в B проехать нельзя: соответствующая клетка пуста. Минимальная стоимость компании тоже равна .

У компании появляется прямой участок E–B. Поэтому маршрут A–E–B стоит . Маршрут A–C–B стоит , а A–C–E–B — , . Наименьшее значение у компании равно .

Сравниваем три минимума: , и ; . Значит, самые дешёвые перевозки из A в B предлагает третья компания.

Ответ

-я компания: маршрут A–E–B стоит .

Помогло?

Номер §2.4 № 6