Slingshot

题目描述

Farmer John 最讨厌的农活之一就是搬运大量牛粪。为了简化这一过程，他想出了一个有趣的点子：与其用拖拉机后面拖着车在两点之间运输粪便，为什么不使用一个巨大的“粪便弹弓”把它射到空中呢？（当然，这能出什么问题呢……）

Farmer John 的农场沿着一条笔直的长路建造，因此农场上的任何位置都可以用它在这条路上的位置来描述（等价于数轴上的一个点）。FJ 建造了 $N$ 个弹弓（$1 \leq N \leq 10^5$），其中第 $i$ 个弹弓由三个整数 $x_i$、$y_i$ 和 $t_i$ 描述，表示该弹弓可以把粪便从位置 $x_i$ 发射到位置 $y_i$，总共只需要 $t_i$ 单位时间。

FJ 有 $M$ 堆粪便需要运输（$1 \leq M \leq 10^5$）。第 $j$ 堆需要从位置 $a_j$ 移动到位置 $b_j$。用拖拉机运输粪便，移动距离为 $d$ 时需要 $d$ 单位时间。FJ 希望通过在每一堆粪便的运输过程中最多使用一次任意弹弓来减少时间。注意：FJ 驾驶空载拖拉机移动所花的时间不计入总时间。

对于这 $M$ 堆粪便，请你帮助 FJ 确定在运输过程中最多使用一次弹弓的前提下，可能的最小运输时间。

输入格式

输入第一行包含 $N$ 和 $M$。接下来 $N$ 行每行用整数 $x_i$、$y_i$、$t_i$ 描述一个弹弓（$0 \leq x_i, y_i, t_i \leq 10^9$）。最后 $M$ 行描述需要移动的粪便堆，每行包含整数 $a_j$ 和 $b_j$。

输出格式

输出 $M$ 行，每行对应一堆粪便，表示运输它所需的最少时间。

2 3
0 10 1
13 8 2
1 12
5 2
20 7

4
3
10

提示

这里，第一堆粪便需要从位置 1 移动到位置 12。 不使用弹弓时，需要 11 单位时间。 然而，使用第一个弹弓时，先花 1 单位时间把粪便移动到位置 0（弹弓起点），再花 1 单位时间将粪便发射到空中并落在位置 10（弹弓终点），然后再花 2 单位时间把粪便移动到位置 12。 第二堆粪便在不使用任何弹弓的情况下移动最好；第三堆粪便应使用第二个弹弓移动。

题目来源：Brian Dean

标签: USACO|2018|Platinum

来源

USACO|2018|Platinum