Tim and Ray are planning a trip to find their friend Sam in Pingtung. To reach their destination as cheaply as possible, they want to minimize the total cost of traveling. On the way, they may stop at a specific location to enjoy the scenery before heading to their final destination. Fortunately, Prof. C has provided them with a limited number of Uber vouchers that allow them to skip the traveling cost of certain roads entirely.
Problem Description
You are given a map consisting of N cities and M undirected roads. Each road has a specific traveling cost (weight).
Key Rules:
Vouchers (K): You have exactly K Uber vouchers.
Using a Voucher: One voucher can be used to traverse any one road. When a voucher is used, the cost for that specific road is treated as 0.
Standard Travel: If you do not use a voucher, you must pay the full cost of the road.
Goal: Find the minimum total cost required to travel from the Starting City to Destination City 1, and then continue from Destination City 1 to Destination City 2.
Constraints
1 ≤ N ≤ 100
1 ≤ M ≤ 150
0 ≤ K ≤ 3
1 ≤ costi ≤ 100
Cities are represented by integers (from 0 to N-1).
NOTE:
You may use any headers from the C++ Standard Library
Testcases
|
1-2 |
K=0 |
|
3-4 |
K=1 |
|
5-6 |
K<=3 |
|
7-8 |
K<=3, Two destination |
For this practice I only provide 1 testcase for every category (Total 4 testcases)
|
Correct Cases |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
Score Given |
30 |
45 |
60 |
70 |
80 |
88 |
95 |
100 |
The first line contains three integers:
N M K
N: number of cities
M: number of undirected roads
K: number of vouchers
The next M lines each contain:
Cityu Cityv costi
This represents an undirected road between Cityu and Cityv with cost costi.
Cityu and Cityv must be different.
Both cities are guaranteed to appear in the city list.
The last line contains three integers:
StartCity EndCity1 EndCity2
Tim and Ray must visit EndCity1 first, then move to EndCity2.
StartCity is different from EndCity1.
EndCity1 can be the same as EndCity2 (in which case, the journey ends at EndCity1).
Print a single integer: the minimum total cost to complete the journey StartCity → EndCity1 → EndCity2.
If the journey is impossible, print -1.