Description
Given an undirected graph and a source vertex s, compute the minimum distance of each node from s. We may assume the label of s is always 0, and then the other nodes in the graph are labeled respectively by 1, 2, ..., n.
Input
The input format:
n, m := number of nodes, number of edges
x1 y1
x2 y2
...
xm ym := the m edges
For each case, the first line contains two integers n and m. Then m lines follow. Each line contains two integers x and y, denoting there is an edge between x and y. There is at most one edge between two nodes.
There are many cases in the input. Cases are separated by a blank line. Input will be terminated by EOF (End-Of-File).
Problem size :
1066: 1 <= n <= 15
1067: 1 <= n <= 200
1068: 1 <= n <= 1000
0 <= m <= n*(n-1)/2
Note that there are exactly n+1 nodes, including the source node 0.
For this problem, any algorithm with time complexity O(n2) is accepted.
You can download the testdata and test your program, we do not use the same data to test your program.
Output
The output format:
5 4 1 - 3 2 1 2 1 4 ... #
where the ith number is the min distance between node i with s (node 0) and "-" indicates such a node is unreachable from s, and "#" indicates end of each case.
.jpg)
For this case, the output is:
1 2 - 1 2 #