# algorithm in java with shorter path

It is assumed that air fares will increase considerably in the coming weeks. The cost of a ticket may depend not only on the distance travelled, but also on the costs to be borne by the airlines.

For this reason it is required to design an algorithm that can come to the aid of travellers, helping them to buy air tickets in a "creative" way, using if necessary only parts of tickets with stops in various cities to obtain low cost travel. However, the airlines, trying to inhibit this type of behaviour, require that the journey covered by a ticket is carried out in order and without intermediate trips. For example, if you have a ticket for travel from City-1 to City-2 and then City-3, you are not allowed to use only the portion of the ticket for travel from City-2 to City-3. You must always start from the first city on your ticket. Also, you are not permitted to travel from City-1 to City-2, fly elsewhere and return, and then continue your journey from City-2 to City-3.

Consider an example. Suppose you are allowed to purchase three types of tickets:

Ticket No. 1: City-1 to City-3 to City-4 € 225.00

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

Ticket n. 3: from City-2 to City-3 € 50.00

Suppose you want to travel from City-1 to City-3. There are two ways to get there using only the choices of

tickets available:

Buy ticket no. 1 for € 225,00 and use 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 variety of ticket offers and one or more travel itineraries, you need to determine how to purchase your tickets to minimize the cost of travel.

input/output:

The input consists of a sequence of ticket offers and a series of routes of

journey to make.

The sequence starts with a line containing N, the number of ticket offers, followed by N descriptions, one per line. Each description consists of a real positive number specifying the ticket price, the number of cities in the ticket itinerary, and then the list of cities. Each city is identified by a positive integer number. Note that you can buy more than one ticket in the same offer.

The next line contains L, the number of routes whose cost must be minimized. The following L lines indicate the planned route. Each line consists of the number of cities on the itinerary (including the departure city), 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.

-a ticket cannot be purchased several times

-a city cannot be found several times in the same ticket

Skills: Java, Algorithm Analysis, Algorithm

( 0 reviews ) Italy

Project ID: #25649251

## 15 freelancers are bidding on average €56 for this job

urmate

Hi there I am a senior software engineer with 10 years of practical programming experience. I have excellent programming and development skills in various programming languages and frameworks. I am interested in your More

€100 EUR in 2 days
(368 Reviews)
7.0
iridescent2x15

Hi I have done many java projects. Kindly contact to share more details about your project in chat. We can negotiate the price. Thank you

€150 EUR in 7 days
(69 Reviews)
6.1

Hey! My name is Vladimir, I'm an experienced competitive programmer (also a student at the University of Cambridge), and I'm quite experienced in Java. I can do this project in less then an hour, feel free to contact More

€30 EUR in 1 day
(8 Reviews)
3.3
bomerb

Hello. I have 10+ years of Java programming experience. I have read your project description. I really like algorithm puzzles. I wish we can work together. I will be here for chatting the details.

€100 EUR in 3 days
(9 Reviews)
3.4
johnkaleke

hi.... I have gone through your project description ,and I can confirm that i can deliver it as expected. I have an extensive experience programming with excellent **********PHP,JAVA,PYTHON/Django ,C,C#,C++ ********** More

€130 EUR in 5 days
(4 Reviews)
3.5
uzairnaseer920

I am interested in this job Kindly reply me soon so we can discuss more about this. Thanky you ...............

€19 EUR in 7 days
(5 Reviews)
2.6
workgaman

✨✨✨✨✨ I CAN FINISH IT FOR A HOUR ✨✨✨✨✨ I have just read your requirement very carefully so I understood what you want fully. I am sure that I can finish it for 1 hour because I am a professional C/C++/C#, Javascript ex More

€100 EUR in 1 day
(2 Reviews)
2.7

Hello, I went through your problem and it's a typical case where mathematical modeling (mixed integer programming) could be used to obtain optimal solution. I have a lot of experience on that. Will be happy to help Tha More

€30 EUR in 7 days
(3 Reviews)
2.2
n4taklyukina

Hello, I am really interested in your project. Especially I have rich experience in C/C++, Python, Machine Learning Algorithm. If you need, I can show you my previous work. I can work full time in your time zone and I More

€25 EUR in 1 day
(2 Reviews)
1.9
dev034

I know java and DSA. Therefore I can solve this problem in optimum Tim and produce a solution in Java.

€25 EUR in 1 day
(0 Reviews)
0.0
aniketkumar9052

Hey there I have read the description and i know exactly what you want and can do this work for you.I have 8 years of experience in this [login to view URL] forward to work with you. Thanks

€29 EUR in 4 days
(0 Reviews)
0.0
govindarajanr

Hello there, I hope you are doing great and in the best of health & high spirits. My name is Govindarajan R. I am an experienced Fullstack developer, which includes experience in the technologies required for the tas More

€25 EUR in 3 days
(0 Reviews)
0.0
akashmujawdia

Dear Project Owner, My self Akash. I am working as a Java Developer. I have 3.5 years of experience in Java including Core Java, Servlets JSP,Rest Api,Spring Core, Spring MVC, Spring Boot,Spring Security,Junit,Hiberna More

€50 EUR in 1 day
(0 Reviews)
0.0
aliraza9990

Respected Sir/Madam I have read your work requirements and willing to implement your task. I have 2+ years of experience in java programming, algorithms. I m new here so i haven't any review yet. Please allow me to sho More

€20 EUR in 7 days
(0 Reviews)
0.0
bhavan27494779

I am an algorithm expert. This can be proven by my profile in competitive programming. I am an expert in codeforces ( [login to view URL] ). I have 6 stars in problem-solving in hackerrank (htt More

€10 EUR in 1 day
(0 Reviews)
0.0