Имеется N городов, соединенных двухсторонними дорогами. Для каждой дороги задана ее протяженность в километрах. Машина может поворачивать (изменять направление движения) только в городах. Машина имеет бак вместимостью Z литров бензина и для нее задан расход бензинаX литров на один километр. В некоторых городах имеются заправочные станции. У каждой заправочной станции задана своя стоимость 1 литра бензина. В не зависимости от того, сколько бензина осталось в баке машины, на заправке доливается бензин в бак до его полного заполнения. Машина сможет заправиться только в том случае, если ее бак заполнен менее, чем на половину.
Необходимо определить самый дешевый маршрут из города A в город B, если первоначально бак машины заполнен полностью.
Пусть М - макс. заполненность бака.
Вообще она решается так. Строится граф. Вершина в графе - это пара (город, заполненность бака).
Теперь, пусть у тебя есть дорога из города А в город Б, и расстояние между ними требует С галонов бензина. Тогда делаешь для любой заполненности бака i от С до М делаешь ребро в графе из (А,i) в (Б,i-C) со стоимостью ноль (ты не платишь за то, что ты едешь, ты платишь, когда покупаешь бензин). Ну и соответственно в каждом городе из любой заполненности бака меньше половины делаешь ребро в полную заполненность со стоимостью, равной стоимости такой заправки.
Дальше пускаешь дийкстру.
Вообще в оригинале в этой задаче заправляться можно было из любой заполненности в любую, но решение от этого не сильно меняется.