Problem S. 36. (May 2008)
S. 36. The railway network in a country has the following properties:
-there is only one track between two neighbouring stations, so a train can overtake another one only at the stations
-crossings only occur at the stations
-the network is connected, so it is possible to travel between any two cities by rail
-each train moves with the same constant speed everywhere.
After the structure of the network and current positions of the trains are given, your program should create a timetable: it should specify the route for each train to reach their destinations, and the travelling time for the last train to arrive is minimal.
The railway network (Vasúthálózat in the figure) is given in a text file: each line contains the code letter of two cities and the travelling time between them, separated by spaces. There are at most 25 cities, denoted by capital letters of the English alphabet. Each travelling time is less than 100 minutes. Positions of trains (Vonatok in the figure) are also given in a text file: each line contains the letter of a city (the current position of certain trains), and each further letter denotes the destination of a train currently staying in that city. These letters are also separated by spaces.
Your program should specify for each city and train the departure times and routes. The timetable (Menetrend in the figure) should be written into a text file with each line containing the departure time in minutes (relative to the start of the simulation), the initial and destination cities of the train (two letters without a space), further the letters of the two cities (without a space) through which the train travels. The other output text file should contain the arrival time (Érkezés in the figure) of each train and letters of the initial and destination cities (without a space). Both output files should be sorted according to time instants and periods in increasing order. The four command line parameters of your program are the following: name of the input file describing the railway network, name of the input file describing the trains, finally the output files describing the timetable and arrival times.
The source code of your program (s36.pas, s36.cpp, ...) together with a short documentation (s36.txt, s36.pdf, ...) should be submitted, also containing a brief description of your solution and the name of the developer environment to use.
Deadline expired on June 16, 2008.
1 student sent a solution. 4 points: 1 student.