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

Question

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.

Answer 1

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.

Answer 2

https://code.sololearn.com/c0j0wk4AUNK2/#cpp

Answer 3

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

Answer 4

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.

Answer 5

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.