数据结构代写 | COMP9024 20T2 Assignment

这个作业是用图数据结构模拟交通网络并计算路径、时间等
COMP9024 20T2 Assignment

Objectives
The assignment aims to give you more independent, self-directed practice with
advanced data structures, especially graphs
graph algorithms
asymptotic runtime analysis
Schedules
Next, your program should ask the user for the number m of busses, trains and light rail vehicles running
during a day, followed by m schedules. Each schedule requires the number of stops, k≥2, followed by
k*2 lines of the form:
hhmm
stop-name
meaning that passengers can get on or off at that time (hh – hour, mm – minute) at that stop. An example
is:
Enter the number of schedules: 2
Enter the number of stops: 5
1640
UNSW
1645
Kensington
1705
Central
1708
Chinatown
1715
Wynyard
Enter the number of stops: 2
1645
UNSW
1700
Central
You may assume that:
The input is syntactically correct: 4 digits, then a new line with the name of a stop.
All times are valid and range from 0000 to 2359.
Stops are input in the right (temporal) order.
There are no overnight connections: Each bus, light rail or train will reach its final stop before
midnight.
Only valid stops that have been input before will be used.

Stage 1 (3 marks)
For stage 1, you should demonstrate that you can read the input and generate a suitable data structure.
For this stage, all test cases will only use queries (From, To, DepartAt) for which
there is only one bus, train or light rail service connecting From and To ; and
this is guaranteed to depart on, or after, the requested time, DepartAt .
Hence, all you need to do for this stage is find and output this direct connection, including all stops along
the way and the arrival/departure times. Here is an example to show the desired behaviour of your
program for a stage 1 test:
prompt$ ./goNSW
Enter the total number of stops on the network: 7
Wynyard
QVB
Central
Kensington
UNSW
Glebe
Broadway
Enter the number of schedules: 2
Enter the number of stops: 5
0945
Wynyard
0950
QVB
1000
Central
1022
Kensington
1027
UNSW
Enter the number of stops: 2
1459
Broadway
1518
Glebe
From: Broadway
To: Glebe
Depart at: 0950
1459 Broadway
1518 Glebe
From: QVB
Stage 2 (5 marks)
For stage 2, you should extend your program for stage 1 such that it always finds, and outputs, a
connection between From and To that
departs on, or after, the requested time DepartAt ; and
arrives as early as possible.
You should assume that:
Changing takes no time: Passengers arriving at a stop can get onto any other train, bus or light rail
service that leaves that stop at the same time or later.
In all test scenarios there will be at most one connection that satisfies all requirements.
If there is no connection, the output should be:
No connection found.