Задание 4. Информатика. ОГЭ. Ушаков 2025-2
- Просмотры: 86
- Изменено: 15 января 2025
Между пунктами \(A, \, B, \, C, \, D, \, E, \, F\) построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 8 | 3 | 12 | 16 | ||
| B | 6 | 9 | 2 | 4 | ||
| C | 8 | 6 | 4 | 2 | 10 | |
| D | 3 | 9 | 4 | 8 | ||
| E | 12 | 2 | 2 | 8 | 8 | |
| F | 16 | 4 | 10 | 8 |
Определите длину кратчайшего пути между пунктами \(A\) и \(F.\) Передвигаться можно только по дорогам, протяжённость которых указана в таблице, два раза посещать один пункт нельзя.
Решение:
Python
INF = float('inf')
W = [(INF, INF, 8, 3, 12, 16),
(INF, INF, 6, 9, 2, 4),
(8, 6, INF, 4, 2, 10),
(3, 9, 4, INF, 8, INF),
(12, 2, 2, 8, INF, 8),
(16, 4, 10, INF, 8, INF)]
N = len(W)
def opt_way(way, end, cur_len = 0):
cur = way[-1]
if cur == end:
return cur_len
min_len = INF
for x in range(N):
if x not in way:
min_len = min(min_len, opt_way(way + [x], end, cur_len + W[cur][x]))
return min_len
print(opt_way([0], 5))
Ответ: \(15\)