#PU816. USACO 2018 February Contest, Platinum — Problem 1. Slingshot

    ID: 1383 传统题 文件IO:slingshot 2000ms 256MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>USACO赛事:feb18来源:usaco.orgscoring:equal_test_cases

USACO 2018 February Contest, Platinum — Problem 1. Slingshot

USACO 2018 February Contest, Platinum — Problem 1. Slingshot

题目描述

One of the farming chores Farmer John dislikes the most is hauling around lots of cow manure. In order to streamline this process, he comes up with an intriguing idea: instead of hauling manure between two points in a cart behind his tractor, why not shoot it through the air with a giant manure slingshot? (indeed, what could possibly go wrong...) Farmer John's farm is built along a single long straight road, so any location on his farm can be described simply using its position along this road (effectively a point on the number line). FJ builds NN slingshots (1≤N≤1051 \leq N \leq 10^5), where the iith slingshot is described by three integers xix_i, yiy_i, and tit_i, specifying that this slingshot can shoot manure from position xix_i to position yiy_i in only tit_i total units of time. FJ has MM piles of manure to transport (1≤M≤1051 \leq M \leq 10^5). The jjth such pile needs to be moved from position aja_j to position bjb_j. Hauling manure with the tractor for a distance of dd takes dd units of time. FJ is hoping to reduce this by allowing up to one use of any slingshot for transporting each pile of manure. Time FJ spends moving his tractor without manure in it does not count. For each of the MM manure piles, please help FJ determine the minimum possible transportation time, given that FJ can use up to one slingshot during the process.

输入格式

The first line of input contains NN and MM. The next NN lines each describe a single slingshot in terms of integers xix_i, yiy_i, and tit_i (0≤xi,yi,ti≤1090 \leq x_i, y_i, t_i \leq 10^9). The final MM lines describe piles of manure that need to be moved, in terms of integers aja_j and bjb_j.

输出格式

Print MM lines of output, one for each manure pile, indicating the minimum time needed to transport it.

数据范围

(见题面原文)

样例

样例 1

2 3
0 10 1
13 8 2
1 12
5 2
20 7
4
3
10
Here, the first pile of manure needs to move from position 1 to position 12. 
Without using an slingshot, this would take 11 units of time.  However, using
the first slingshot, it takes 1 unit of time to move to position 0 (the
slingshot source), 1 unit of time to fling the manure through the air to land at
position 10 (the slingshot destination), and then 2 units of time to move the
manure to position 12.  The second pile of manure is best moved without any
slingshot, and the third pile of manure should be moved using the second
slingshot.
Problem credits: Brian Dean