Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Dijkstra shortest path algorithm with edge cost

I have a directed, positive weighted graph. Each edge have a cost of use. I have only A money, i want to calculate shortest paths with dijkstra algorithm, but sum of edges costs on route must be less or equal to A.

I want to do this with most smallest Dijstra modification (if I can do it with small modification of Dijkstra). I must do this in O(n*log(n)) if I can, but i think i can.

Anyone can help me with this?

like image 927
Svisstack Avatar asked Apr 26 '10 00:04

Svisstack


1 Answers

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

The problem was given at CEOI '98 and its official solution can be found here.

like image 161
IVlad Avatar answered Sep 20 '22 19:09

IVlad