Problem doubt

general
1

This question is from past contest of Expedia contest on InterviewBit, which is over now.

There are N cities numbered 1 to N. From each city, there are exactly N flights connecting to other cities. Srijesh hates travelling on flights but he had no other option as he has to reach city N from city 1. You are given the details of flights from each city i.e. if there are 3 flights from city ‘x’ say(‘A’,‘B’,‘C’) then there are 3 flights from city x that will go to city ‘A’,‘B’,‘C’.
Find the minimum number of flights he has to take to reach city N from city 1.
If there is no possible way to reach city N from city 1, output -1.
Constraints: 1<=M<N<=1000 1<=A[i][j]<=N
Example- A=[[2,4],[4,3],[5,2],[3,1],[1,4]]
Output- 3.
Explanation- He can choose flights from city 1->2, 2->3 and 3->5. He can also choose flights from city 1->4, 4->3 and 4->5. The minimum number of flights taken is 3.

Can anyone help in this question?

2

Use Breadth-first search

5

This problem is basically a single source shortest path problem on an directed, unweighted graph.

You can just use a BFS algorithm or a DFS algorithm starting at node 1 and use the fact that distance of a node = 1 + distance of parent node.

Initialise all distances as say 0 and then test for 0 to see if it’s unreachable.