Company: Samsung Research
Difficulty: medium
Interstellar II Execution time: 5sec(C/C++/JAVA), 15sec(Python) within for maximum 50 test cases combined Memory: maximum 256MB is available for heap, global, and static combined (Note that maximum 1MB is available for stack) Submissions: 10 times Evaluation criteria: The number of correct test cases The era of traveling the great universe through the use of wormholes has come. All of the locations in the universe are given as 2-dimensional coordinates of (X, Y). The spacecraft can only move to the parallel directions to the X-axis or Y-axis and it takes 1 second to move 1 distance. Therefore, the time that the spacecraft needs to move from (x1, y1) to (x2, y2) is as follows: Time = |x2 - x1| + |y2 - y1| There are N wormholes in the outer space. Ki, the time to pass through each wormhole, is different for each. The wormhole can be passed through bi-directionally. For the sake of convenience, the two entrances of the wormhole can be called Gate A and Gate B. Not all wormholes have to be