+ 2

# K friends want to meet in a city. Find the smallest amoutn of gas they need.

We have N cities and M both-way roads. K friends that live in a specified city want to get to another city(called Z). Every road costs 1 unit of gas. If 2 or more friends meet in a city they can continue the road using only 1 car(I guess someone abandons his car XD). The cars have an infinite space(meaning that there is an infinite number of friends that can travel in a single car). Print the minimum amount of gas they need to get to Z or minus 1 if one or more friends can't get there. I tried using the Dijkstra's algorithm to compute the amount of gas every single friend need to get from their city to Z. I calculated the sum of those results. After that I also stored the road they used to get to Z and then I looked at their roads and computed how many friends have passed through the same node, so that I could substract from the earlier sum (no. friends -1), meaning that only one car consumed gas there, not no friends cars. It seems to not work(it only gets 10/100 points). I was wondering if someone can help me, or tell me what is wrong with my idea. Have great day! :) P.S: there can be a maximum of 10 friends, and a maximum of 200 cities.

2nd Feb 2020, 1:42 PM
Stefan Secrieru
+ 2
What you said earlier would be the Travelling Salesman Person problem, if I am not mistaking. I start from somewhere and I have to go through some cities before the actual destination.
2nd Feb 2020, 3:41 PM
Stefan Secrieru
2nd Feb 2020, 1:43 PM
Stefan Secrieru
+ 1
blackwinter Here is an example: N= 5 M= 4 K= 3 Z= 5 List of friends: 1 2 3 The arcs 1 4 2 4 3 4 4 5 The cost of every arc is one. Expected output: 4
2nd Feb 2020, 3:10 PM
Stefan Secrieru
+ 1
Maybe I wrote something wrong, but you do not have to start from a node and take all the friends, it is not like carpooling. Every friend start moving towards the destination and if 2 or more meet they dump one of the car and go together. So the route here would be : 1-4 and 2-4 and 3-4 and then all three of them go from 4 to 5 so 4 units of gas.
2nd Feb 2020, 3:39 PM
Stefan Secrieru
+ 1
But here everyone starts moving in the same time. If they couldn't dump the cars the answer would be a sum of Dijkstra's minimum roads.
2nd Feb 2020, 3:42 PM
Stefan Secrieru