Блог пользователя dev_il

Автор dev_il, 15 лет назад, По-русски
есть вот такая задача..не могу её уже давно решить, т.к. совсем не знаю как подойти..был бы рад хоть каким-нибудь содержательным подсказкам =)

Имеется  N городов, соединенных двухсторонними дорогами. Для каждой дороги задана ее протяженность в километрах. Машина может поворачивать (изменять направление движения) только в городах. Машина имеет бак вместимостью Z литров бензина и для нее задан расход бензинаX литров на один километр. В некоторых городах имеются заправочные станции. У каждой  заправочной станции задана своя стоимость 1 литра бензина. В не зависимости от того, сколько бензина осталось в баке машины, на заправке доливается бензин в бак до его полного заполнения. Машина сможет заправиться только в том случае, если ее бак заполнен менее, чем на половину.

      Необходимо определить самый дешевый маршрут из города A в город B, если первоначально бак машины заполнен полностью.

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Содержательная подсказка - динамическое программирование
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Не знаю, как предлагает artie решать ее динамикой
Пусть М - макс. заполненность бака.
Вообще она решается так. Строится граф. Вершина в графе - это пара (город, заполненность бака).
Теперь, пусть у тебя есть дорога из города А в город Б, и расстояние между ними требует С галонов бензина. Тогда делаешь для любой заполненности бака i от С до М делаешь ребро в графе из (А,i) в (Б,i-C) со стоимостью ноль (ты не платишь за то, что ты едешь, ты платишь, когда покупаешь бензин). Ну и соответственно в каждом городе из любой заполненности бака меньше половины делаешь ребро в полную заполненность со стоимостью, равной стоимости такой заправки.
Дальше пускаешь дийкстру.
Вообще в оригинале в этой задаче заправляться можно было из любой заполненности в любую, но решение от этого не сильно меняется.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да уж, умею я мысли излагать :) Под динамикой подразумевалось как раз нечто подобное. Видимо, сходство заключалось в состоянии (город, количество бензина).
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    ммм..cool =) .. просто нет слов. сам бы я кажется до такого никогда в жизни не додумался :-(
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а может так: если деревнях нельзя разворачиваться, тогда убрать их вообще, и соединить города напрямую(в обе стороны), поменяв стоимость проезда, а дальше Дейкстрой.
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    стоп, а причем тут деревни? только в городах то есть только не на дорогах?  простите ошибочка, ну все равно Дейкстра))
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
недавно решал примерно такую называется "Заправки" на acmp.