Path length
Problem
In an undirected graph, you want to find the length of the shortest path between two vertices.
Input:
- the first line of the input contains the number N - the number of vertices in the graph (\(1<=N<=100\));< br />
- next, the adjacency matrix is written from a new line (0 indicates the absence of an edge, 1 - the presence of an edge);
- the last line contains the numbers of two vertices - start and end.
Output: Print the length of the shortest path. If the path does not exist, print a single number -1.
Examples
| # |
Input |
Output |
| 1 |
5
0 1 0 0 1
1 0 1 0 0
0 1 0 0 0
0 0 0 0 0
1 0 0 0 0
3 5
|
3 |