INGRED - Ingredients


You are given n cities with m bi-directional roads connecting them and the length of each road. There are two friends living in different cities who wish to collect some ingredients available at different stores to make cake. There are s such stores. They need not come back home after purchasing the ingredients. Petrol is expensive and they would hence like to travel minimum total distance (sum of distance distance traveled by both kids). Help them find out what this distance is.

Input Format:

n m
(m lines of the form ai bi ci)
Here n is number of cities, m is number of roads, ai and bi are the cities(0 indexed) the roads connect and ci is the length of this road
s where s is the number of stores
(1 line containing s space separated integers indicating the city number in which the stores are located.)
(two space separated integers indicating the cities in which the two kids live)

Output Format:

Single integer x where x is the minimum distance that the duo will travel that is minimum sum of distance travelled by first kid and second kid.

Constraints:

2 ≤ n ≤ 100
1 ≤ m ≤ (n*(n-1))/2
0 ≤ a,b < n
0 ≤c≤ 1000
1 ≤ s ≤ 8

Sample Input:

5 6
0 1 5
1 4 1
0 4 10
0 2 2
1 2 3
2 3 4
2
2 4
0 1

Sample Output:

3


Problem Setter: Vidit Gupta


hide comments
mahmud2690: 2017-02-19 19:30:20

all of the s stores must be visited or not?

~!(*(@*!@^&: 2016-08-27 06:40:48

Should be clear that each boy has to buy exactly s items; or both of them will buy s items?

Last edit: 2016-08-27 06:41:09
Shubhojeet Chakraborty: 2016-06-01 20:59:47

lesson learnt..sort the array before using next_permutation.

ISHANI: 2014-09-29 15:09:11

Really Awesome Problem.
tricky test case which will help you:
5 6
0 1 5
0 2 2
0 4 10
1 3 5
1 2 3
1 4 10
3
2 4 3
0 1
ANS->19

Last edit: 2014-09-29 15:09:55
785227: 2014-06-15 19:16:48

Awesome problem. Enjoyed solving it :)

maradona: 2014-02-08 09:13:09

-edit-

Last edit: 2015-07-31 18:19:41
praveen123: 2014-02-08 09:13:09

Increase the font size please

mehmetin: 2014-02-08 09:13:09

--

Last edit: 2014-02-03 13:24:24

Added by:darkshadows
Date:2014-01-28
Time limit:1s-2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64