Note: the key part is how to convert this problem to the shortest path problem: 1) how to build the graph and how many graphs to build; 2) how to decide the source and destination; and 3) how to assign the weight on the edge.

Please write a unique program using basic Java and keep it simple.

Tomorrow morning Jill must travel from Hamburg to Darmstadt to compete in the regional programming contest. Since she is afraid of arriving late and being excluded from the contest, she is looking for the train which gets her to Darmstadt as early as possible. However, she dislikes getting to the station too early, so if there are several schedules with the same arrival time then she will choose the one with the latest departure time. Jill asks you to help her with her problem. You are given a set of railroad schedules from which you must compute the train with the earliest arrival time and the fastest connection from one location to another. Fortunately, Jill is very experienced in changing trains and can do this instantaneously, i.e., in zero time!

The very first line of the input gives the number of scenarios. Each scenario consists of three parts. The first part lists the names of all cities connected by the railroads. It starts with a number 1 < C ≤ 100, followed by C lines containing city names. All names consist only of letters. The second part describes all the trains running during a day. It starts with a number T ≤ 1,000 followed by T train descriptions. Each of them consists of one line with a number ti ≤ 100 and then to more lines, each with a time and a city name, meaning that passengers can get on or off the train at that time at that city. The final part consists of three lines: the first containing the earliest possible starting time, the second the name of the city where she starts, and the third with the destination city. The start and destination cities are always different.

For each scenario print a line containing “Scenario i”, where i is the scenario number starting from 1. If a connection exists, print the two lines containing zero padded timestamps and locations as shown in the example. Use blanks to achieve the indentation. If no connection exists on the same day (i.e., arrival before midnight), print a line containing “No connection”. Print a blank line after each scenario.

Sample Input
0949 Hamburg
1006 Frankfurt
1325 Hamburg
1550 Darmstadt
1205 Frankfurt
1411 Darmstadt
0100 Paris
2300 Tokyo
Sample Output
Scenario 1
Departure 0949 Hamburg
Arrival 1411 Darmstadt
Scenario 2
No connection

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.*;

public class Graph {
    static final int NUM_OF_VERT = 4; //this can be changed of course
    int matrix[][][]; //graph is represented by an adjacency matrix
    private Stack<Integer> Path = new Stack<>();   // the current path
    private ArrayList<Integer> InPath = new ArrayList<>();    // the set of vertices on the path
    private ArrayList<String> AllPaths = new ArrayList<>();    // list of all paths, one of them will be the correct path...

By purchasing this solution you'll be able to access the following files:

50% discount

$100.00 $50.00
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Java Programming Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats