[Help] Graph — Shortest path — gas stations (price of fuel varies)

Правка en1, от a_r_d, 2020-10-31 19:48:48

Given a weighted undirected graph. There are N cities connected by M roads. For each road, you know the fuel needed to travel that road. A small subset of cities have gas station. The price per litre at each gas station is different. The task is to travel from city A to city B in a car with capacity C minimizing the total cost.

Stuck at — Create a new graph including the only the cities with gas stations along with source and destination cities. The edge weights in this graph can be found by multiple runs of Dijkstra's algorithm. Now, how to proceed with different fuel price at each node? Some DP?

Теги #shortest_path, #dynamic programing, #graph

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский a_r_d 2020-10-31 19:51:55 14
en1 Английский a_r_d 2020-10-31 19:48:48 685 Initial revision (published)