Problem 1123 --Shortest path
1123: Shortest pathTime Limit: 3 Sec Memory Limit: 128 MB
Submit: 1754 Solved: 220
Alice has a graph of n nodes and m undirected edges. These nodes are numbered from 1 to n, and now she wants to know the shortest path from node s to other nodes. If there is no path between s and node i, output -1. (1 <= i <= n).
The first line will be an integer T, which is the number of the test cases(1 <= T <= 10). For each test case, the first line will be three integers, n(1 <= n <= 105), m(1 <= m <= 5*105) and s(1 <= s <= n). The following are m lines, and each line will be two integers x and y, which means there is an undirected edge between x and y.
For each test, output numbers in one line. The i-th number means the shortest path between s and node i. If the path does not exist, then print -1 instead.
4 4 1
0 1 2 1