ACAC 题库 ac.isam.top
GitHub
AtCoder Regular Contest-- 219
C
挨家挨户推销员之旅（电梯）
Traveling Door-to-Door Salesman (Elevator)
AtCoder
⌀ 1598
原题
← BD →

挨家挨户推销员之旅（电梯）AI (CI翻译)

Problem Statement

题目描述

AI (CI翻译)

Note: This problem has almost the same setting as Problem G. The differences in the problem statements are shown in red bold.

注意：本题的设定与问题 G 几乎相同。题面中的差异以红色粗体显示。AI (CI翻译)

There is an underground apartment represented by a grid with $H$ rows and $W$ columns. The cell at the $i$-th row from the top and the $j$-th column from the left is denoted as cell $(i,j)$.

有一个地下公寓，可以用一个 $H$ 行 $W$ 列的网格表示。从上往下数第 $i$ 行、从左往右数第 $j$ 列的单元格记为 $(i,j)$。AI (CI翻译)

The entrance to the underground apartment is at cell $(1,1)$.

地下公寓的入口位于单元格 $(1,1)$。AI (CI翻译)

The underground apartment has $N$ doors. The $k$-th door is located at cell $(A_k, B_k)$.

地下公寓中有 $N$ 扇门。第 $k$ 扇门位于单元格 $(A_k, B_k)$。AI (CI翻译)

Inside the underground apartment, a salesman can perform the following two types of moves any number of times, in any order:

在地下公寓内，推销员可以以任意顺序、任意次数执行以下两种移动：AI (CI翻译)

  • He can walk to a horizontally adjacent cell (left or right) from his current cell. The cost of this move is $1$.
  • If his current cell is in column $1$ or column $W$, he can move to a vertically adjacent cell (up or down) by elevator. The cost of this move is $\mathbf{0}$.
  • 他可以从当前单元格向左或向右移动到水平相邻的单元格。该移动的费用为 $1$。
  • 如果当前单元格位于第 $1$ 列或第 $W$ 列，他可以通过电梯向上或向下移动到垂直相邻的单元格。该移动的费用为 $\mathbf{0}$。
AI (CI翻译)

His goal is to start from cell $(1,1)$, repeat moves, visit all $N$ cells with doors at least once, and then arrive at cell $(1,1)$.

他的目标是从单元格 $(1,1)$ 出发，通过重复移动至少访问所有有门的 $N$ 个单元格，最后回到单元格 $(1,1)$。AI (CI翻译)

Find the minimum total cost needed to achieve his goal.

求完成目标所需的最小总费用。AI (CI翻译)

Constraints

约束条件

AI (CI翻译)
  • $1 \leq H \leq 10^9$
  • $2 \leq W \leq 10^9$
  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq A_k \leq H$
  • $1 \leq B_k \leq W$
  • $(A_1, B_1), \dots, (A_N, B_N)$ are distinct.
  • All input values are integers.
  • $1 \leq H \leq 10^9$
  • $2 \leq W \leq 10^9$
  • $1 \leq N \leq 3 \times 10^5$
  • $1 \leq A_k \leq H$
  • $1 \leq B_k \leq W$
  • $(A_1, B_1), \dots, (A_N, B_N)$ 两两不同。
  • 所有输入值均为整数。
AI (CI翻译)

Input

输入格式

AI (CI翻译)

The input is given from Standard Input in the following format:

输入从标准输入按以下格式给出：AI (CI翻译)

H W
N
A_1 B_1
\vdots
A_N B_N

H W
N
A_1 B_1
\vdots
A_N B_N
AI (CI翻译)

Output

输出格式

AI (CI翻译)

Output the answer on a single line.

在一行中输出答案。AI (CI翻译)

样例

Input #1
6 8
7
1 4
2 2
2 7
3 1
6 3
6 4
6 6
Output #1
18
By moving as follows, the goal can be achieved with a total cost of $18$: - Start from cell $(1,1)$. - Move $1$ cell down and $1$ cell right from cell $(1,1)$ to visit cell $(2,2)$ (cost $1$). - Move $1$ cell left and $1$ cell down from cell $(2,2)$ to visit cell $(3,1)$ (cost $1$). - Move $3$ cells down and $2$ cells right from cell $(3,1)$ to visit cell $(6,3)$ (cost $2$). - Move $1$ cell right from cell $(6,3)$ to visit cell $(6,4)$ (cost $1$). - Move $2$ cells right from cell $(6,4)$ to visit cell $(6,6)$ (cost $2$). - Move $2$ cells right, $4$ cells up, and $1$ cell left from cell $(6,6)$ to visit cell $(2,7)$ (cost $3$). - Move $1$ cell right, $1$ cell up, and $4$ cells left from cell $(2,7)$ to visit cell $(1,4)$ (cost $5$). - Move $3$ cells left from cell $(1,4)$ to arrive at cell $(1,1)$ (cost $3$).
Input #2
1000000000 1000000000
2
888888888 600000000
1000000000 700000000
Output #2
1999999998
题目信息
题号
arc219_c
所属比赛
AtCoder Regular Contest-- 219
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有；中文翻译由 AI 生成（gpt-6.1-sol），如有出入请以原文为准。