CODEWITHSUNDEEP
algorithmgraph
Andrew00
Andrew00

Reputation: 23

Minimal car refills on a graph of cities

There's a graph of cities.

n - cities count

m - two-ways roads count

k - distance that car can go after refill

Road i connects cities pi and qi and has length of ri. Between the two cities can be only one road.

A man is going from city u to city v. There are a gas stations in l cities a1, a2, ..., al.

A car starts with a full tank. If a man gets in a city with a gas station, he can refill (full tank) a car or ignore it.

Return value is a minimal count of refills to get from a city u to city v or -1 if it's impossible.

I tried to do it using Dijkstra algorithm, so I have minimal distance and path. But I have no idea how to get minimal refills count

Upvotes: 2

Views: 215

Answers (1)

btilly
btilly

Reputation: 46399

It is slightly subtle, but the following pseudo-code will do it.

First do a breadth-first search from v to find the distance from every city to the target. This gives us a distance_remaining lookup with distance_remaining[city] being the shortest path (without regards to fillup stations).

To implement we first need a Visit data structure with information about visiting a city on a trip. What fields do we need?

city
fillups
range
last_visit

Next we need a priority queue (just like Dijkstraa) for possible visits to consider. This queue should prioritize visits by the shortest possible overall trip that we might be able to take. Which is to say visit.fillups * max_range + (max_range - visit.range) + distance_remaining[visit.city].

And finally we need a visited[city] data structure saying whether a city is visited. In Dijkstra we only consider a node if it was not yet visited. We need to tweak that to only consider a node if it was not yet visited or was visited with a range shorter than our current one (a car that arrived on full may finish even though the empty one failed).

And now we implement the following logic:

make visit {city: u, fillups: 0, range: max_range, last_visit: None}
add to priority queue the visit we just created
while v = queue.pop():
    if v.city == u:
        return v.fillups # We could actually find the path at this point!
    else if v not in visited or visited[v.city] < v.range:
        for each road r from v.city:
            if r.length < v.range:
                add to queue {city: r.other_city, fillups: v.fillups, range:v.range - r.length, last_visit: v}
            if v.city has fillup station:
                add to queue {city: v.city, fillups: fillups + 1, range: max_range, last_visit: v}
return -1

Upvotes: 1

Related Questions