1368 - Problem for RenJianRenAi:: HUST Online Judge

1368 - Problem for RenJianRenAi

Time Limit : 10 Second

Memory Limit : 256 MB

Submission: 84

Solved: 18

Description

RenJianRenAi is a beautiful girl who likes traveling. One day, She takes a tour to a beautiful city A. She wants to stay in city A for m +1 days and she lives in the hotel B1. City A is doing the road construction. So every day there are changes on roads, such as the time taking from one place to another may reduce or increase. A friend of RenJianRenAi also stays in City A, and she lives in hotel B2. Therefore, RenJianRenAi need to take a taxi from B1 to B2 every day, and then play together. In the evening, RenJianRenAi returns to B1.
RenJianRenAi does not want to spend too much time on the road from B1 to B2, she wants to take the least of time. So if you are the driver, you should help her.
Suppose city A is a gridworld map with the height * width size (each point can only be connected with other four neighbor points), please give out a time table between the neighbored points.

Input

There are many test case, please end with EOF.
The first part of the input, initialize the map section, including multi-line, the first line contains two numbers, height, width (≤ 150), on behalf of the size chart.
Each row consists of six numbers, y, x, c1, c2, c3, c4.
Where (y, x) on behalf of coordinates, c1, c2, c3, c4, representing from the (y, x) to (y, x +1), (y +1, x), (y, x-1), ( y-1, x) the time spent, -1 that cannot be reached.
Note: From a point to b point may not be equal to the time points from b to a point to spend time.
-1-1 indicated the end of the first part.
Each change in plans, including multiple lines, each line consists of six numbers, y, x, c1, c2, c3, c4
Where (y, x) on behalf of coordinates (0 <= y < height, 0 <= x < width), c1, c2, c3, c4, representing from the (y, x) to (y, x +1), (y +1, x), (y, x-1), (y-1, x) the time spent -1 that cannot be reached.
To -1-1, said the end of this revised plan

Output

Each test case, containing m +1 rows, said the initial plan the first line to the target node from the starting point for the minimum time, then change the map after m rows represent the minimum time.

sample input

2 2
0 0 4 12 -1 -1
0 1 -1 11 15 -1
1 0 4 -1 -1 7
1 1 -1 -1 1 4
-1 -1
2
0 1 -1 7 3 -1
-1 -1
1 0 1 -1 -1 15
-1 -1

sample output

15
11
11

hint

source

中国地质大学(武汉)第七届ACM程序设计大赛暨华中地区部属高校ACM邀请赛