提示: 欢迎访问OurACM平台。
Problem 1658 Space travel

Accept: 33    Submit: 152
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Dr. J invented a spacecraft, he said, this spacecraft can reach a speed of 1,000 light-years/h.He gave this spacecraft to timeloop, timeloop just dreamed about space travelling.
However, in order to reach other distant galaxies, 1,000 light-years / h speed is too slow for him. But this does not matter. Because, timeloop can use the “wormhole”.What is the wormhole? To put it simply, "wormhole" can connect the remote regions of the universe by using space-time straw. It can connect the parallel universe, and provide the possibility of time travel. It may also be the space-time tunnel connecting white and black hole, also known as "Ash Road." You may think so, the wormhole could let any object from point A move to point B immediately. Timeloop have detected some wormholes through the invention of Dr. J. But he encountered a problem---how can he reach his destination in the shortest distance by using wormholes? Can you help him solve this problem?
In order to make the problem more simply, there are some assumptions:
  • the universe is lied in rectangular coordinates
  • the spaceship can only move following x-coordinate and y-coordinate
  • At the entrance to each wormhole, timeloop can choose to fly into or continue to move forward. If timeloop flys over the wormhole, it takes no effect.
  • The coordinates of a point, it may be common, or the entrance to a wormhole, or the exit of a wormhole. It is not possible for a point belongs to two wormholes
  • his start point is (0,0).

Input

There are multiple tests. For each test, the first line are three integers x,y,N(0<=N<=500), indicating the coordinate of the destination and the number of wormholes respectively. The following N lines, in each line, there are four integers indicating the entrance and exit coordinate of the wormhole. You should note that the wormhole is unidirectional. The coordinate will fit in a signed 32-bit integer.

Output

For each test, output an integer, indicating the shortest distance to the destination.

Sample Input

10 10 1 4 4 9 9 10 10 1 4 4 100 100

Sample Output

10 20

Source

FOJ月赛-2008年10月

Submit  Back  Status  Discuss