I got the following Graph question in the telephonic round of **GOOGLE**:\n**Given a map of N cities,a thief wants to go from a start city to his hometown .An edge between two cities is bidirectional and has a positive weight that represents distance between the two cities.The thief can go from city X to city Y only if the shortest distance from city Y to his hometown is smaller than the shortest distance from city X to the hometown.\nDetermine how many routes are possible from start city to his hometown.\nAssume that start city is city0 and hometown is cityN-1.**\n\nExample :\n**Input** :\nN = 5\nedges = {{u,v,weight}|u,v are vertices}\nE = {{0,1,3},{0,2,3},{1,2,1},{0,3,2},{1,4,2},{2,4,1},{3,4,10}}\n**Output**:\n3\n0-1-4\n0-1-2-4\n0-2-4\n0-3 edge will be rejected since shortest distance between 3 and 4 is 10 > shortest distance between 0 and 4 which is 4.\nCan someone help solving this question?

I got the following Graph question in the telephonic round of GOOGLE:\nGiven a map of N cities,a thief wants to go from a start city to his hometown .An edge be