Apply a shortest path algorithm

It is assumed that airfares increase significantly in the weekend. The cost of a ticket in fact, as well as the distance traveled, may depend on the expenses that the airlines had

For this reason it is required to design an algorithm that can come to the aid of travelers, helping them to buy airline tickets in a "creative" way, if necessary use only parts of tickets with stops at various points

cities to get cheap travel. However, airlines are trying to inhibit this type of behaviors,they require that the journey covered by a ticket be carried out in order and without intermediate travel couplings. For example, if you have a ticket for travel from City-1 to City-2 and then to City-3, is forbidden to use only the part of the ticket for the journey from City-2 to City-3. You must always start from the first city of the ticket.

Let's consider an example. Suppose you are allowed to purchase three types of tickets:

 Ticket no. 1: from City-1 to City-3 to City-4 € 225.00

 Ticket no. 2: from City-1 to City-2 € 200.00

 Ticket no. 3: from City-2 to City-3 € 50.00

Let's say you want to travel from City-1 to City-3. There are two ways to get there using only the ticket choices available:

 Buy ticket no. 1 for € 225.00 and uses only the first leg of the ticket.

 Buy ticket no. 2 for € 200.00 and ticket no. 3 for € 50.

The first choice is the cheapest.

Given a number of flight ticket offers and one or more travel itineraries, it is necessary to determine how to purchase tickets to minimize the cost of travel.

The input consists of a sequence of ticket offers and a series of travel itineraries to be created.

The sequence begins with a line containing N, the number of ticket offers, followed by N descriptions, one per line. Each description consists of a positive real number that specifies the ticket price, the number of cities included in the ticket itinerary, and then the list of cities. Each city is identified by a positive integer. Note it is possible to purchase more than one ticket in the same offer. The next line contains L, the number of itineraries whose cost must be minimized. The following L lines indicate the route foreseen by the itinerary. Each row is composed of the number of cities on the itinerary (including the city of departure), followed by a sequence of numbers representing the cities in the order in which they are to be visited.

For each itinerary, the program must output the number that

distinguishes the itinerary, the minimum cost to be paid and the tickets used for the trip, in the order in which they will be used.

Example 1

INPUT:

3

225 3 1 3 4

200 2 1 2

50 2 2 3

1

2 1 3

OUTPUT: Itinerary 1:

Cost = 225

Ticket N.: 1

Example 2

INPUT:

3

100 2 2 4

100 3 1 4 3

200 3 1 2 3

2

3 1 4 3

3 1 2 4

OUTPUT:

  Itinerary 1:

Cost = 100

Ticket N.: 2

Itinerary 2:

Cost = 300

Ticket N.: 3 1

THE CODE MUST BE LARGELY COMMENTED, YOU HAVE TO EXPLAIN EVERY PART OF THE CODE AND DESCRIBE HOW IT WORKS, THE LANGUAGE IS JAVA

Java

Project ID: #25663457

About the project