The problem can be modeled as an undirected graph G(V, E) with (e), e E being the length of an edge (all lengths are nonnegative) Let (s, t) V be the source and destination vertices respectively and P V is the set of vertices having gas stations Assume s, t P Further, you are given r The task is to find the shortest s t path in G such that the total length of edges between two successive vertices from P along the path is at most r