ICPC TRIP -graph problem

#1

cant understand approach how minimum cost is computed

#2

hi @abhaynit2019

Approach to solve the problem

  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.