Задание 4. Информатика. ОГЭ. Ушаков 2025-1
- Просмотры: 105
- Изменено: 15 января 2025
Между пунктами \(A, \, B, \, C, \, D, \, E, \, F\) построены дороги, протяжённость которых (в километрах) приведена в таблице.
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 7 | 11 | 2 | 15 | ||
| B | 7 | 2 | 7 | 4 | 9 | |
| C | 11 | 2 | 3 | 7 | 8 | |
| D | 7 | 3 | 11 | 3 | ||
| E | 2 | 4 | 7 | 11 | ||
| F | 15 | 9 | 8 | 3 |
Определите длину кратчайшего пути между пунктами \(A\) и \(F.\) Передвигаться можно только по дорогам, протяжённость которых указана в таблице, два раза посещать один пункт нельзя.
Решение:
Python
INF = float('inf')
W = [(INF, 7, 11, INF, 2, 15),
(7, INF, 2, 7, 4, 9),
(11, 2, INF, 3, 7, 8),
(INF, 7, 3, INF, 11, 3),
(2, 4, 7, 11, INF, INF),
(15, 9, 8, 3, INF, 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))
Ответ: \(14\)