Задача о дилижансе. Облегчённая версия

Лёгкое прикосновение к разделу теории графов о кратчайших путях.

Задача кратчайшего пути – задача поиска пути между двумя вершинами на графе, минимизирующего сумму весов рёбер, его составляющих.

Сложность решения, конечно, зависит от того, что нам известно про граф. В общем случае для решения пользуются специальными алгоритмами. В нашей задаче есть изначальные сведения о графе, и требуется только доказать оценку сверху на длину кратчайшего пути.

#олимпиады #графы

На перекладных (#107)