Introduction

In this project, we will be implementing a revised version of Dijkstra's algorithm and using it to solve

a small variation on the shortest path problem. As in the first two projects, there is very little direction

regarding how to design or structure your code. These decisions are, mostly, left to you. Make sure to

start early and to stay organized. Note that this project is a little smaller than previous projects and is

worth a total of $100pts.$

Submissions

a$)$ Your C$++$ solution code $("$project$\_3.$cpp$")$ for this project should be submitted on both inginious

and Canvas.

Notes

There will be more than enough time in lab to discuss these problems in small groups and I highly

encourage you to collaborate with one another outside of class. However, you must write up your

own solutions independently of one another. You also need to start with the skeleton file give on

Canvas $($rename it to "project$\_3.$cpp$").$ Do not post solutions in any way.

The Problem

You are a software engineer at a nameless electric vehicle company working as part of a team on a tool

for helping customers plan road trips. Charging stations are not yet as widely available as gas stations

so$,$ when determining a route from the starting point to the destination, the range of the vehicle must

be considered. With summer approaching, your team is scrambling for a solution to this problem. Using

your knowledge of graphs and shortest path algorithms, propose and implement an efficient algorithm

for determining the shortest path between two cities paying attention to vehicle range and available

charging stations.

Inputs$/$Outputs

Input will come from cin.

The first line will contain four space separated integers, $n,m,c,$ and $i.**n$ is the number of nodes in the graph.

$m$ is the number of edges in the graph.

$c$ is the maximum distance in miles the vehicle can travel on a full charge.

$i$ is the range of the vehicle with its initial charge.

The second line contains a pair of integers, start and end, indicating the start and end nodes

for the trip.

The following $n$ lines contain pairs of space separated integers, $v$ and $s,$ representing nodes.

$v$ is the name of a node. This will be an integer between $0$ and $n-1.$

$s$ is $1$ if the node $v$ has a charging station and $0$ otherwise.

The following $m$ lines each contain three space separated integers, $u,v,$ and $d,$ representing

edges.

$u$ and $v$ are edge endpoints.

$d$ is the distance in miles between nodes $u$ and $v.$

Print output to cout.

The output will have two lines.

The first line should be "Verify Path: $1"$ when a suitable path exists.

The second line should be the length of the trip followed by a colon, the start state, the

sequence of charging stations visited on the trip, and the end state.

This sequence should be space separated, should start with start, and should end with

end.

This sequence should represent a shortest path given the constraints. Ties will be broken

between the paths with the same distance by the sum of the ids of the nodes along each path $($in

ascending order, which means the path of the smallest sum wins.$)$

If no suitable path exists, print $"$No suitable path from start to end exists" where start and

end are node ids.

For example, the graph below corresponds to the input: $4757$

$6754$

Output in this case should be:

Verify Path: $1$

$133$: $047$

Grading

$(30$ pts$)$ An implementation of Dijkstra's algorithm.

$(50$ pts$)$ A solution to the given problem, based on the percentage of test cases passed on

inginious.

$.(10$ pts$)$ A function bool verifyPath$($Graph $G,$ vectori$>$ path, int $i,$ int $c$ Initialize all the nodes; specifically, for the starting node, initialize its distance

as $0,$ its fuel $($remaining charge$)$ as the initial charge, and its history $($path$)$ as

empty.

Initialize an empty vector allP aths to store the found solution paths. $($It is a

vector of paths$)$

Initialize a variable min$\_$distance as INT$\_$MAX,

While the priority queue is not empty, perform the following steps:

a$.$ Pop the top node from the priority queue.

b$.$ Get the node ID$,$ distance, fuel, and history.

c$.$ If the current distance is greater than min$\_$distance, break the loop.

d$.$ If the node ID is equal to the end node ID$,$ add the path history to

allPaths, and update min$\_$distance with the minimum of min$\_$distance

and the current distance.

e$.$