시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 129 | 45 | 39 | 35.780% |
With our time on Earth coming to an end, Cooper and Amelia have volunteered to undertake what could be the most important mission in human history: travelling beyond this galaxy to discover whether mankind has a future among the stars. Fortunately, astronomers have identified several potentially inhabitable planets and have also discovered that some of these planets have wormholes joining them, which effectively makes the travel distance between these wormhole connected planets zero. For all other planets, the travel distance between them is simply the Euclidean distance between the planets. Given the location of Earth, planets, and wormholes, find the shortest travel distance between any pairs of planets.
For each test case, output a line, “Case i:”, the number of the ith test case. Then, for each query in that test case, output a line that states “The distance from planet1 to planet2 is d parsecs.”, where the planets are the names from the query and d is the shortest possible travel distance between the two planets. Round d to the nearest integer.
3 4 Earth 0 0 0 Proxima 5 0 0 Barnards 5 5 0 Sirius 0 5 0 2 Earth Barnards Barnards Sirius 6 Earth Proxima Earth Barnards Earth Sirius Proxima Earth Barnards Earth Sirius Earth 3 z1 0 0 0 z2 10 10 10 z3 10 0 0 1 z1 z2 3 z2 z1 z1 z2 z1 z3 2 Mars 12345 98765 87654 Jupiter 45678 65432 11111 0 1 Mars Jupiter
Case 1: The distance from Earth to Proxima is 5 parsecs. The distance from Earth to Barnards is 0 parsecs. The distance from Earth to Sirius is 0 parsecs. The distance from Proxima to Earth is 5 parsecs. The distance from Barnards to Earth is 5 parsecs. The distance from Sirius to Earth is 5 parsecs. Case 2: The distance from z2 to z1 is 17 parsecs. The distance from z1 to z2 is 0 parsecs. The distance from z1 to z3 is 10 parsecs. Case 3: The distance from Mars to Jupiter is 89894 parsecs.