旅行者走在提瓦特大陆上~~~
TA接下来有 n 个任务要做,第 i 个任务所要到达的地点坐标为(x_i, y_i)
旅行者从坐标 (sx, sy) 处出发,需要依次到达这 n 个地点。地点 u 到地点 v 花费的代价为他们之间的曼哈顿距离
当然,大陆上有 m 座传送锚点,第 i 座锚点的坐标为(a_i, b_i)。
旅行者可以以 0 的代价在任何时候,任何地点传送到任意一座锚点。
求旅行者完成所有任务需要的最小花费。
第一行两个正整数 n,m。
第二行包含两个整数 sx, sy。
接下来的 n 行每行包含两个整数 x_i, y_i 为第 i 个任务的地点坐标。
再接下来的 m 行每行包含两个整数 a_i, b_i 为第 i 个传送锚点的坐标。
完成所有任务的最小花费。
3 3 0 0 1 1 1 2 10000 10000 100001 100001 1000 100 10000 10000
3
对于 20% 的数据,保证 1≤ n, m ≤ 100。
对于 100% 的数据,保证 1≤ n, m ≤ 1000, -10^9 ≤ a_i, b_i, x_i, y_i ≤ 10^9。
时间限制 | 1 秒 |
内存限制 | 128 MB |