#P1639. [USACO18FEB] Teleportation B

[USACO18FEB] Teleportation B

题目描述

Farmer John 最讨厌的农活是运输牛粪。为了精简这个过程,他制造了一个伟大的发明:便便传送门!与使用拖拉机拖着装满牛粪的大车从一个地点到另一个地点相比,他可以使用便便传送门将牛粪从一个地点瞬间传送到另一个地点。

Farmer John 的农场沿着一条长直道路而建,所以他农场上的每个地点都可以简单地用该地点在道路上的位置来表示(相当于数轴上的一个点)。一个传送门可以用两个数 xxyy 表示,被拖到地点 xx 的牛粪可以瞬间传送到地点 yy,反之亦然。

Farmer John 想要将牛粪从地点 aa 运输到地点 bb,他建造了一个可能对这一过程有所帮助的传送门(当然,如果没有帮助,他也可以不用)。请帮助他求出他需要使用拖拉机运输牛粪的总距离的最小值。

输入格式

输入仅包含一行,为四个用空格分隔的整数:aabb,表示起始地点和结束地点,后面是 xxyy,表示传送门。所有的位置都是范围为 01000\ldots 100 的整数,不一定各不相同。

输出格式

输出一个整数,为 Farmer John 需要用拖拉机运输牛粪的最小距离。

3 10 8 2
3

提示

在这个样例中,最佳策略是将牛粪从位置 33 运到位置 22,传送到位置 88,再运到位置 1010。 所以需要用拖拉机的总距离为 1+2=31 + 2 = 3