Scribd
Upload
4 views1 page

Minimize Family Vacation Travel Costs

A family is traveling between cities in a country on a limited budget. They must travel from a source city to a destination city, choosing the minimum cost route between connected cities that allows for at most one luxury train ride. The problem is to plan the family's trip to minimize their total travel costs given the network of cities and costs of normal and luxury train routes between them.

Uploaded by

codeforces
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd
4 views1 page

Minimize Family Vacation Travel Costs

A family is traveling between cities in a country on a limited budget. They must travel from a source city to a destination city, choosing the minimum cost route between connected cities that allows for at most one luxury train ride. The problem is to plan the family's trip to minimize their total travel costs given the network of cities and costs of normal and luxury train routes between them.

Uploaded by

codeforces
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as ODT, PDF, TXT or read online on Scribd

PROBLEM DESCRIPTION

A family going on a vacation have a limited budget. They have to travel a country
starting from one city which is the source and ending at another city which is the
destination. There are 'n' cities in the country and 'm' roads connecting the cities. For
each of the roads connecting two cities , there is also an alternate path connecting
those two cities. This alternate route is the luxury train route. The money that is spent
via the normal route and the luxury train route between the two cities is given.
Now the family wants to reach their destination by spending the minimum amount
possible. Also they can have at most one luxury train ride in their journey. So as their
trip adviser you have to plan the trip such that cost is minimized.

Input format:
First line contains 't', the number of test cases. For each test case:
The first line contains 'n' and 'm' denoting the number of cities and number of roads
respectively.
The next 'm' lines contains four integers,'u','v','c1' and 'c2' ,where u and v are the cities
which are connected by normal route(whose cost to travel is 'c1') and the luxury train
route(whose cost is 'c2').
The last line contains tow integers denoting the source and the destination respectively.

Output format:
For each test case,output the minimum travel cost if the destination is reachable. If the
destination is not reachable from the source print -1.

Sample Input:
1
44
1 2 10 4
1379
2435
3434
14

Sample Output:
7

You might also like