Условие:
ст\%20Вокруг\%20информатики\%202025/B6\%20-\%20Европа/В6-1\%20-\%20Каналы\%20Венеции.pdf
МЭШ
Задача B6-1. Каналы Венеции
На основе данных из интернета Роболис составил таблицу, в которой отметил, от какой точки к какой мы можем плыть. В первом столбце указана начальная точка, в первой строке - конечная точка каждого участка пути. Числа в таблице - время в минутах, которое придется затратить на этот участок пути.
| A | B | C | D | E | F | G | H | I | |
|---|---|---|---|---|---|---|---|---|---|
| A | - | 10 | 15 | 8 | 0 | 0 | 0 | 0 | 0 |
| B | 0 | - | 0 | 0 | 10 | 0 | 0 | 0 | 0 |
| C | 0 | 3 | - | 0 | 12 | 3 | 11 | 21 | 0 |
| D | 0 | 0 | 0 | - | 13 | 0 | 9 | 0 | 0 |
| E | 0 | 0 | 0 | 0 | - | 16 | 11 | 0 | 11 |
| F | 0 | 0 | 0 | 0 | 0 | - | 11 | 10 | 12 |
| G | 0 | 0 | 0 | 0 | 0 | 0 | - | 6 | 16 |
| H | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - | 6 |
| I | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | - |
Однако местный житель говорит, что нам нужно избегать пунктов, обозначенных в таблице как Е и F: сейчас в этих точках скопление лодок, и мы можем попасть в «пробку».
Сейчас мы находимся в точке А. Попасть нам нужно в точку, которая обозначена буквой І. Следуя совету местного жителя, мы не будем выбирать пути, включающие в себя точку F или E. Мы не будем выбирать кратчайший путь (как зто делают обычно), мы выберем самьй интересный маршрут! По словам местного жителя, это тот, который займет ровно 38 минут. Он такой только один!