ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs ContestProblemSetList
Login Register

问题 D: 接两个牛棚

内存限制：128 MB 时间限制：1 S
题面：传统 评测方式：文本比较 上传者：
提交：59 通过：14
返回比赛提交提交记录

题目描述

# [USACO21DEC] Connecting Two Barns S

## 题目描述

Farmer John 的农场由 $N$ 块田地（$1 \leq N \leq 10^5$）组成，编号为 $1 \ldots N$。在这些田地之间有 $M$ 条双向道路（$0 \leq M \leq 10^5$），每条道路连接两块田地。

农场有两个牛棚，一个在田地 1 中，另一个在田地 $N$ 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地 $i$ 和 $j$ 之间建造新道路的花费是 $(i-j)^2$。

请帮助 Farmer John 求出使得牛棚 $1$ 和 $N$ 可以相互到达所需要的最小花费。

输入格式

每个测试用例的输入包含 $T$ 个子测试用例（$1\le T\le 20$），所有子测试用例必须全部回答正确才能通过整个测试用例。

输入的第一行包含 $T$，之后是 $T$ 个子测试用例。

每个子测试用例的第一行包含两个整数 $N$ 和 $M$。以下 $M$ 行，每行包含两个整数 $i$ 和 $j$，表示一条连接两个不同田地 $i$ 和 $j$ 的道路。输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的 $N+M$ 之和不超过 $5 \cdot 10^5$。


输出格式

输出 $T$ 行。第 $i$ 行包含一个整数，为第 $i$ 个子测试用例的最小花费。

## 样例 #1

### 样例输入 #1

```
2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
```

### 样例输出 #1

```
2
1
```

## 提示

【样例解释】

- 第一个子测试用例中，最优的方式是用一条道路连接田地 2 和 3，用一条道路连接田地 3 和 4。
- 第二个子测试用例中，最优的方式是用一条道路连接田地 3 和 4。不需要第二条道路。

【数据范围】

- 测试点 2 满足 $N \le 20$。
- 测试点 3-5 满足 $N \le 10^3$。
- 测试点 6-10 没有额外限制。

输入样例 复制 

2
5 2
1 2
4 5
5 3
1 2
2 3
4 5

输出样例 复制 

2
1

数据范围与提示

In the first sub-test case, it is optimal to connect fields 2 and 3 with a path, and fields 3 and 4 with a path.

In the second sub-test case, it is optimal to connect fields 3 and 4 with a path. No second path is needed.

SCORING:

  • Test case 2 satisfies N≤20.
  • Test cases 3-5 satisfy N≤103.
  • Test cases 6-10 satisfy no additional constraints.

分类标签