I need hints and suggestions for Problem 2034 Caravans on Timus Online Judge. I could not find a proper explanation for the problem online. Problem on Timus 2034

Only clues that I could get is to do two BFS from node s and d and get the nodes that lie on the shortest path and now is stuck how to calculate the answer from this.

thanks for any help.