Problem Statement: Finding the flight itinerary to reach the destination at earliest possible time.

Write a Java or C$++$ program that can handle the following.

Suppose you want to leave from Baton Rouge airport $($BTR$)$ and reach Providence $($PVD$).$ You can leave as

early as $9$:$30$ am in the morning. You want to find out an itinerary which results in you reaching PVD at

the earliest possible time. You will write Graph.java or Graph.cpp which will take command line

arguments $$BTR PVD $0930$ will output the itinerary:

EV $5210$ BTR ATL $11451413$

DL $1112$ ATL PVD $15061728$

This means $1728($or $5$:$28$ pm$)$ is the earliest time we can reach PVD among all possible flight itineraries.

More specifically, you are given two files:

$$ airports.txt: There are $307$ unique airport codes.

$$ flights.txt: These are $13950$ flights which operate $($or once operated$)$ daily between US airports.

You will model this as a graph. Each airport will be a vertex and each flight will be an edge. Notice that

there may be multiple edges between same two vertices. Also, these edges are directed. Instead of

weight $($as in distance for the regular Dijkstra$$s algorithm$),$ here each edge is annotated with departure

time and arrival time. Regardless of these differences, we can modify Dijkstra$$s algorithm for this

purpose.

Usual Dijkstra$$s algorithm minimizes distance, and each vertex v has an associated distance value d$($v$)$

that stands for shortest distance from source s to v as we know so far based on the edges explored. In

the case of flight itinerary, d$($v$)$ or dvalue stands for earliest possible time we can reach v based on flights

data explored so far.

Input File: Input files $($flights$.$txt and airports.txt$)$ will be provided separately. Your program

should take $3$ command line arguments $($Source airport, Destination airport and beginning time$).$

For example, let$$s take two airports, Miami $($MIA$)$ and Tulsa County $($TUL$).$ The three$-$letter

codes of the airports and beginning time will be passed as command line arguments as follows.

$$ C$++$ Program

Compile: g$++-$o Graph Graph.cpp

Run: $./$Graph MIA TUL $0500$

$$ Java Program

Compile: javac Graph.java

Run: java Graph MIA TUL $0500$

Output: For the gradescope submission, the output should be the number representing the

earliest possible arrival time, followed by a newline. For example, the itinerary for the above$-$

mentioned input i$.$e$.,$ source $=$ MIA, destination $=$ TUL and beginning time $=0500$ is

AA $281$ MIA DFW $600814$

AA $96$ DFW STL $820955$

WN $3660$ STL TUL $10151130$

Your code on gradescope submission should display only $1130$ as the final output followed by a newline.

Submission: This is a group project. You may create a group of up to $2$ people. Please mention

names of all the team$-$members as a comment at the top of your code. Also, mention this by making a

group$-$submission on gradescope. For this, on the Manage Submissions page, in the bottom action bar,

click 'Group Members' to add the other group member. Submit the file Graph.cpp or Graph.java to

gradescope. Gradescope will run few custom test cases and return the result of the test. If everything

goes well, you will get full credit. Additionally, if it fails, then you can submit it as many times as you want

before the deadline.