USACO翻译：USACO 2014 DEC Silver三题

不念不忘少年蓝@ 2022-01-10 03:53 183阅读 0赞

## USACO 2014 DEC SILVER ##

一、题目概览

<table> 
 <tbody> 
 <tr> 
 <td> 中文题目名称 </td> 
 <td> 回程 </td> 
 <td> 马拉松 </td> 
 <td> 奶牛慢跑 </td> 
 </tr> 
 <tr> 
 <td> 英文题目名称 </td> 
 <td> piggyback </td> 
 <td> marathon </td> 
 <td> cowjog </td> 
 </tr> 
 <tr> 
 <td> 可执行文件名 </td> 
 <td> piggyback </td> 
 <td> marathon </td> 
 <td> cowjog </td> 
 </tr> 
 <tr> 
 <td> 输入文件名 </td> 
 <td> piggyback.in </td> 
 <td> marathon.in </td> 
 <td> cowjog.in </td> 
 </tr> 
 <tr> 
 <td> 输出文件名 </td> 
 <td> piggyback.out </td> 
 <td> marathon.out </td> 
 <td> cowjog.out </td> 
 </tr> 
 <tr> 
 <td> 每个测试点时限 </td> 
 <td> 1秒 </td> 
 <td> 1秒 </td> 
 <td> 1秒 </td> 
 </tr> 
 <tr> 
 <td> 测试点数目 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 </tr> 
 <tr> 
 <td> 每个测试点分值 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 <td> 10 </td> 
 </tr> 
 <tr> 
 <td> 比较方式 </td> 
 <td> 全文比较 </td> 
 <td> 全文比较 </td> 
 <td> 全文比较 </td> 
 </tr> 
 </tbody> 
</table>

二、运行内存限制

<table> 
 <tbody> 
 <tr> 
 <td> 运行内存上限 </td> 
 <td> 128 M </td> 
 <td> 128 M </td> 
 <td> 128 M </td> 
 </tr> 
 </tbody> 
</table>

** **

**1.****回程****\{piggyback\}**

【问题描述】

Bessie 和 Elsie在不同的区域放牧，他们希望花费最小的能量返回谷仓。从一个区域走到一个相连区域，Bessie要花费B单位的能量，Elsie要花费E单位的能量。

如果某次他们两走到同一个区域，Bessie 可以背着 Elsie走路，花费P单位的能量走到另外一个相连的区域，满足P<B+E。

相遇后，他们可以一直背着走，也可以独立分开。

【文件输入】

第一行，五个不超过40,000的正整数B, E, P, N和M。其中N表示区域的个数（区域分别用1..N编号，N>=3）,M表示各个区域之间连接的双向边的边数。一开始Bessie在区域1， Elsie在区域2，谷仓在区域N。

接下来M行，每行二个整数表示一条双向边连接两个区域，输入保证从区域1和区域2都能走到区域N。

【文件输出】

一行，一个整数，最小花费的单位能量。

【输入样例】

4 4 5 8 8

1 4

2 3

3 4

4 7

2 5

5 6

6 8

7 8

【输出样例】

【样例说明】

Bessie从1到4，Elsie从2到3到4，然后一起从4到7到8。

**2.** **马拉松****\{marathon\}**

【问题描述】

Bessie参加城市马拉松比赛，要顺序经过N (3 <= N <= 500)个检查点，其中检查点1是起点，检查点N是终点。    Bessie尝试略过K(K < N)个检查点，以减少总路程，检查点1和检查点N不能被略过。两个检查点的距离是|x1-x2| + |y1-y2|。

【文件输入】

一行，两个整数N 和 K。

接下来N行，每行两个整数X和Y，(-1000 <= x <= 1000, -1000 <= y <= 1000)，表示N个检查点的坐标，这N个检查点是按顺序给出的，所以必须被按顺序经过。注意，同一个检查点可能会多次出现，当某次Bessie略过该检查点时，他只能略过当前的一次，而不是同时略过该检查点的所有出现次数。

【文件输出】

一行，一个整数，表示Bessie经过的总路程。

【输入样例】

5 2

0 0

8 3

1 1

10 -5

2 2

【输出样例】

【样例说明】

略过检查点(8, 3) and (10, -5)。