a_r_d's blog

By a_r_d, history, 5 weeks ago, In English

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 fuel capacity C minimizing the total cost.

Stuck at — Create a new graph including 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?

 
 
 
 
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What are the restrictions of N, M and C?

One possible idea is represent each vertex as a pair (v, f), where 1 <= v <= N and 0 <= f <= C. And build a graph that, if v has a gas station then it can go from (v, f) a (v, f + a), where f + a <= C, with cost equal to a * (price of fuel in city v), and can go from (v, f) to (u, f — w) with cost 0, where w is the necessary fuel to travel from v to u. Finally, perform a Dijkstra.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I think your solution is correct. The constraints were (2<=N<=1000) (1<=M<=10000) (1<=C<=100000) (1<=no.of cities with gas station <=120). So finally we'll have 120*100000 states but the number of edges in this solution might be too large.