Сверь числа и знаки с фото.
- Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость перевозок между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Стоимость перевозок по маршруту складывается из стоимостей перевозок между соседними станциями. Перевозки между населёнными пунктами A, B, C, D, E осуществляют три компании, представившие стоимость своих услуг в табличной форме. Какая компания обеспечивает минимальную стоимость перевозок из A в B?
A B C D E A X 3 1 B X 4 2 C 3 4 X 2 D 1 X E 2 2 X
A B C D E A X 3 1 1 B X 4 C 3 4 X 2 D 1 X E 1 2 X
A B C D E A X 3 1 4 B X 4 2 C 3 4 X 2 D 1 X E 4 2 2 X
Краткий ответ: минимальную стоимость обеспечивает третья компания: \(6\). Лучший маршрут — \(A\to E\to B\): \(4+2=6\). У первой и второй компаний минимум по \(7\).
Как читать таблицу. Каждая непустая клетка вне диагонали — это ребро графа: например, \(A-C=3\) означает дорогу \(A-C\) стоимостью \(3\). Таблицы симметричны, поэтому графы неориентированные. \(D\) — концевая станция: из неё можно уехать только в \(A\), поэтому в маршрут \(A\to B\) она не входит.
Графы компаний
1-я компания
B
/ \
4/ \2
/ \
A ──3── C ──2── E
│
1
│
D
Рёбра: \(A-C=3\), \(A-D=1\), \(B-C=4\), \(B-E=2\), \(C-E=2\).
Возможные маршруты:
- \(A-C-B=3+4=7\)
- \(A-C-E-B=3+2+2=7\)
Минимум: \(7\).
2-я компания
B
│4
│
D ──1── A ──3── C
\ /
1\ /2
\ /
E
Рёбра: \(A-C=3\), \(A-D=1\), \(A-E=1\), \(B-C=4\), \(C-E=2\).
Маршруты:
- \(A-C-B=3+4=7\)
- \(A-E-C-B=1+2+4=7\)
Минимум: \(7\).
3-я компания
C ──4── B
/ \ /
3/ \2 /2
/ \ /
A ──4── E
│
1
│
D
Рёбра: \(A-C=3\), \(A-D=1\), \(A-E=4\), \(B-C=4\), \(B-E=2\), \(C-E=2\).
Маршруты:
- \(A-C-B=3+4=7\)
- \(A-C-E-B=3+2+2=7\)
- \(A-E-B=4+2=6\)
Минимум: \(6\).
Проверка: \(7\), \(7\), \(6\). Значит, минимальную стоимость даёт компания 3.