Кратчайший путь в grid графе

[daniel19]

Помогите, пожалуйста. Очень срочно необходимо решить следующую задачу:

Дан граф-сетка размеров NxM
Пусть веса всех горизонтальных дуг [(i, j) → (i + 1, j)] зависят только от j, а веса всех вертикальных дуг [(i, j) → (i, j + 1)] зависят только от i. Таким образом, веса полностью заданы, если указаны n «горизонтальных» весов uj и m «вертикальных» весов vi, и длина входа равна в этом случае O(M + N).
Построить оптимальный линейный O(M+ N)-алгоритм поиска самого «легкого» пути между вершинами (0, 0) и (N, M) для этого класса грид-графов.


Заранее спасибо!

[Deggial]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
Причина переноса: формулы не оформлены $\TeX$ом

Наберите формулы $\TeX$ом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).
После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.