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

Стоимость маршрута — сумма стоимостей перевозок между соседними станциями. Пустые ячейки означают, что прямого пути между станциями нет.

1. Компания 1: маршрут A—C—B стоит 3 + 4 = 7. Маршрут A—C—E—B также стоит 3 + 2 + 2 = 7. Минимальная стоимость — 7.

2. Компания 2: маршрут A—C—B стоит 3 + 4 = 7. Маршрут A—E—C—B стоит 1 + 2 + 4 = 7. Минимальная стоимость — 7.

3. Компания 3: маршрут A—E—B стоит 4 + 2 = 6. Для сравнения, маршрут A—C—B стоит 3 + 4 = 7. Минимальная стоимость — 6.

Ответ: наименьшую стоимость перевозки из A в B — 6 — предлагает компания 3.