Алгоритм кратчайшего пути Дейкстры со стоимостью ребра

Question

У меня есть ориентированный положительный взвешенный график. У каждого края есть стоимость использования. У меня есть только деньги, я хочу рассчитать кратчайшие пути с алгоритмом Дейкстры, но сумма затрат на ребра на маршруте должна быть меньше или равна A.

Я хочу сделать это с самой маленькой модификацией Dijstra (если я могу сделать это с маленькой модификацией Dijkstra). Я должен сделать это в O(n*log(n)), если смогу, но я думаю, что смогу.

Кто-нибудь может мне помочь с этим?

Answer 1

https://www.spoj.pl/problems/ROADS/

Проблема была дана на CEOI '98 , и ее официальное решение можно найти здесь .

Answer 2

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

Конечно, вы всегда можете замкнуть внутренний контур, если вы посещаете путь, стоимость которого превышает A.

РЕДАКТИРОВАТЬ: С разъяснением того, что вы хотите минимизировать стоимость и расстояние, вы не сможете сделать это без уточнения решения, которое вы хотите. Хотите самый дешевый путь? Хотите кратчайший путь? Вы хотите какую-то функцию стоимости и расстояния? Все это определяет, какую весовую функцию вы должны использовать для определенного ребра.