Hipercijevi
레이팅 미적용의견: 0
\(5^{th}\) round, February \(16^{th}\), 2013
In a galaxy far, far away, the fastest method of transportation is using hypertubes. Each hypertube
directly connects K stations with each other. What is the minimum number of stations that we need to
pass through in order to get from station 1 to station N?
The first line of input contains three positive integers: N (\(1 \le N \le 100\,000\)), the number of stations, K
(\(1 \le K \le 1\,000\)), the number of stations that any single hypertube directly interconnects, and M (\(1 \le M\)
≤ 1 000), the number of hypertubes.
Each of the following M lines contains the description of a single hypertube: K positive integers, the
labels of stations connected to that hypertube.
The first and only line of output must contain the required minimum number of stations. If it isn't
possible to travel from station 1 to station N, outp\(ut -1\).
9 3 5
1 2 3
1 4 5
3 6 7
5 6 7
6 8 9415 8 4
11 12 8 14 13 6 10 7
1 5 8 12 13 6 2 4
10 15 4 5 9 8 14 12
11 12 14 3 5 6 1 133Clarification of the first example: It is possible to travel from station 1 to station 9 using only four
stations in the following ways: 1-3-6-9, or 1-5-6-9.
평가 및 의견
Hipercijevi
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Hipercijevi