The ear of traveling 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). Spacecraft can only move to parallel direct
ion to the X-axis or Y-axis and it takes 1 second to move 1 dist
ance. 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 t
hrough each wormhole, is different for each. The wormhole can be
passed through bi-directionally.
For the sake of convenience, two entrances of wormhole can be ca
lled Gate A and Gate B.
Gate A <------ Ki seconds (1<= i <= N) -----> Gate B
Not all wormholes have to be used to reach the destination point
Also, it is okay if none of the wormholes are used. It is also o
kay not to use a wormhole even though the spacecraft gets to the
point of a wormhole.
Given the starting and destination point(location) of spacecraft
and information of each wormhole, find the minimum time from the
starting to the destination point.
[Constraints]
1. The number of wormholes, N, is greater or equal to 0 and less
than or equal to 5.
2. The time to pass through a wormhole, 0<= Ki <=3000
3. X,Y the coordinate of the universe: 0<= X,Y <= 1000
4.
[Input]
5 //Number of test case
0 //Test 1, N=0
0,0,60,60 //(x1,y1)=(0,0), (x2,y2)=(60,60)
1 //Test 2, N=1
0 0 2 0 //(0,0) => (2,0)
1 0 1 2 0 //1st wormhole, Gate A(1,0), Gate B(1,2), Ki=0
1
0 0 60 60
40 40 20 20 10
2
100 50 10 5 //(100,50) => (10,5)
80 40 10 6 10
80 10 70 40 5
3
500 500 1000 1000
501 501 999 999 1000
1 1 499 499 100
1000 999 0 0 200
[Output]
#1 120
#2 2
#3 90
#4 41
#5 305
