Как в ЕГЭ · 14 из 20

№23. Самый выгодный путь

По мотивам задания №23, вторая его половина — оптимальный путь. Курьер едет по односторонним дорогам, и на каждой знает, сколько заработает за доставки по пути. Какой путь из склада в конечный пункт приносит больше всего — и сколько разных путей приносят ровно столько же? Самая выгодная дорога на первом шаге не обязательно ведёт к самому выгодному пути.

Что сделать

Найдите наибольший заработок на пути из start в finish и число путей с таким заработком.

Что приходит

rebra — дороги: тройки (откуда, куда, заработок), заработок — целое, бывает отрицательным
start и finish — откуда и куда

Что вернуть

Пару (наибольший заработок, сколько путей его дают); если пути нет — None.

Допишите функцию luchshiy_put в редакторе справа. Результат верните через return — то, что напечатано, на проверку не влияет.

Пример

Дороги А→Б за 5, А→В за 1, Б→Г за 1, В→Г за 9. Путей два: через Б — 5 + 1 = 6, через В — 1 + 9 = 10. Ответ (10, 1), хотя на первом шаге дорога в Б выгоднее.

Тот же пример кодом

Вызов

luchshiy_put([("А", "Б", 5), ("А", "В", 1), ("Б", "Г", 1), ("В", "Г", 9)], "А", "Г")

Вернуть

(10, 1)

Ctrl+Enter — проверить

Обсуждение

Вопросов пока нет.

Войдите, чтобы спросить.