ICPC Trip - Interesting Graphs Problem!

#1

in this video i did not understand any thing and i watched video many time
so how i solve this problem ?

I am not able to solve the problem i tried my best but not able to solve
#2

Hello @khemchandrs

How to solve this problem is

  1. Apply dijsktra’s from src vertex considering only the train costs and let us call the shortest cost array from src vertex to every other vertex be costFromSrc[]; // SHORTEST TRAIN COST FROM SRC

  2. Apply dijsktra’s from destination vertex considering only the train costs and let us call the shortest cost array from destination vertex to every other vertex be costFromDest[]; // SHORTEST TRAIN COST FROM DEST

  3. Run two loops

    int minFare = costFromSrc["destVertex"];
for(int i = 0; i < V; i++) {
   for(int k = 0; k < V; k++) {
       minFare = min(minFare, costFromSrc[i] + costFromDest[k] + flightFare[i][k]);
   }
}

What the above code do is for the flight between each i->k (i & k are vertices), if ((cost from src to i (through train) + cost from i to k through flight + cost from k to destination ) < minFare)
Then update minFare to be the least.

3 Likes
Complexity issue
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.