P6887: 连接两个谷仓
传统题
1.000s
时间限制
512MB
内存限制
3 提交
2 解决
【题目描述】
【题目描述】
Farmer John
的农场由 N
块田地（1≤N≤10^5
）组成，编号为 1…N
。在这些田地之间有 M
条双向道路（0≤M≤10^5
），每条道路连接两块田地。
农场有两个牛棚，一个在田地 1
中，另一个在田地 N 中。Farmer John 希望确保有一种方式可以沿着一组道路在两个牛棚之间行走。 他愿意建造至多两条新道路来实现这一目标。由于田地的位置因素，在田地 i
和 j 之间建造新道路的花费是 (i−j)^2
。
请帮助 Farmer John
求出使得牛棚 1 和 N 可以相互到达所需要的最小花费。
【
输入格式】
（从终端 /
标准输入读入）：
每个测试用例的输入包含 T
个子测试用例（1≤T≤20），所有子测试用例必须全部回答正确才能通过整个测试用例。
输入的第一行包含 T
，之后是 T
个子测试用例。
每个子测试用例的第一行包含两个整数 N
和 M。以下 M
行，每行包含两个整数 i 和 j
，表示一条连接两个不同田地 i
和 j 的道路。输入保证任何两个田地之间至多只有一条道路，并且所有子测试用例的 N+M 之和不超过 5×10
^5
。
【
输出格式】
（输出至终端 /
标准输出）：
输出 T
行。第 i
行包含一个整数，为第 i
个子测试用例的最小花费。
【
输入样例】
：
2
5 2
1 2
4 5
5 3
1 2
2 3
4 5
【
输出样例】
：
2
1
第一个子测试用例中，最优的方式是用一条道路连接田地 2
和 3，用一条道路连接田地 3 和 4。
第二个子测试用例中，最优的方式是用一条道路连接田地 3
和 4。不需要第二条道路。
【
测试点性质】
：
测试点 2
满足 N≤20。
测试点 3-5
满足 N≤10^3
。
测试点 6-10
没有额外限制。