-->
当前位置:首页 > 题库

PROGRAMMING:Shortest path

Luz5年前 (2021-05-10)题库412
Given an undirected graph with n vertices and e edges, the vertices are numbered from 0 to n − 1. Please determine whether there is a path between the given two vertices. If it exists, the shortest path length is given.
Here, the shortest path length from vertex to itself is defined as 0.
When searching, it is assumed that we always start from the smallest vertex and access the adjacent points in ascending order.
###Input format:
Input the first line to give two integers n (0 < n ≤ 10) and E, which are vertex number and edge number of graph respectively.
Then E lines, each of which gives two vertices of an edge. The numbers in each line are separated by one space.
The last line gives two vertex numbers I, J (0 ≤ I, J < n), separated by spaces.
###Output format:
If there is a path between I and j, output "the length of the shortest path between I and j is X." and X is the shortest path length,
Otherwise, "there is no path between I and J." is output.
###Input sample 1:
```in
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 3
```
###Output sample 1:
```out
The length of the shortest path between 0 and 3 is 2.
```
###Input sample 2:
```in
7 6
0 1
2 3
1 4
0 2
1 3
5 6
0 6
```
###Output sample 2:
```out
There is no path between 0 and 6.
```







answer:If there is no answer, please comment