Предложите алгоритм (график -возможно NP -Завершено)

Имеется сеть городов, соединенных дорогами различной целочисленной длины.

Путешественник хочет поехать на своей машине из одного города в другой. Однако он не хочет минимизировать пройденное расстояние; вместо этого он хочет свести к минимуму расходы на бензин в пути. Бензин можно купить в любом городе, однако каждый город поставляет бензин по различным (целочисленным )ценам (, поэтому кратчайший маршрут не обязательно является самым дешевым ). 1 единица бензина позволяет ему проехать 1 единицу расстояния. Его машина может вместить столько бензина в бак,и он может выбрать, сколько единиц бензина покупать в каждом городе, через который он проезжает. Найдите минимальную стоимость бензина.

Кто-нибудь знает эффективный алгоритм, который можно использовать для решения этой проблемы? Даже название проблемы такого типа было бы полезно, чтобы я мог исследовать ее сам! Очевидно, что это не совсем то же самое, что задача поиска кратчайшего пути. Любые другие советы приветствуются!

РЕДАКТИРОВАТЬ -реальная проблема, с которой я столкнулся, гласит, что будет <1000 городов; <10000 дорог; а емкость бензобака будет где-то между 1 и 100.