In Progress

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.


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

See more: simulated annealing algorithm java explained, ford fulkerson algorithm java, tree algorithm java, dijkstra algorithm java adjacency matrix, dijkstra's shortest path algorithm -- java code, java program to find shortest path between two nodes, printing paths in dijkstra’s shortest path algorithm java, shortest path problem, dijkstra's algorithm java 2d array, dijkstra algorithm java github, dijkstra algorithm java geeksforgeeks, algorithm java project, example genetic algorithm java, bellman ford algorithm java, genetic algorithm java working, scheduling project algorithm java, works process scheduler algorithm java, shortest path algorithm java swing, job scheduling algorithm java, bankers algorithm java application

About the Employer:
( 0 reviews ) Italy

Project ID: #25649251

Awarded to:


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)

11 freelancers are bidding on average €40 for this job


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
(367 Reviews)

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
(7 Reviews)

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)

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)

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
(2 Reviews)

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)

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)

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)

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)

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)