# 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

Про роботодавця:
( 1 відгук ) Turin, Italy

ID Проекту: #25663457

## 5 фрілансерів(-и) у середньому готові виконати цю роботу за €25

hello I am mashud, expert in java. I will complete this project in 1 days perfectly. please contact me to discuss more about the project. thanks.

€34 EUR за 1 день
(8 відгуків(и))
4.1

Hey mate! I am an experienced competitive programmer ([login to view URL] vladamg98, [login to view URL] VladaMG98), and I'm studying Computer Science at the University of Cambridge. I can do your project very quick, as I'm prof Більше

€35 EUR за 1 день
(6 відгуків(и))
3.1
uzairnaseer920

Hello there I am interested in this job. I have experienced person to contact with following field. Kindly reply me soon so we can discuss more about this. Thanky you

€12 EUR за 1 день
(4 відгуків(и))
2.4
mayankgulati21

Hi I have the working algorithm for your problem - i.e to find the cheapest way to complete the journey using the given flights. And now implementing it in Java and delivering it to you shouldn't take more than a day. Більше

€30 EUR за 2 дні(-в)
(0 відгуків(и))
0.0
vincentjdelacruz

Hello, I am a graduate of the University of Toronto in Canada and would enjoy the opportunity to work on your project. I was excited reading the project details as it is problems just like this that we were solving ba Більше

€14 EUR за 2 дні(-в)
(0 відгуків(и))
0.0