레이팅 미적용농부 존의 농장은 \(1 \ldots N\)으로 편리하게 번호가 붙은 \(N\)개의 들판 \((1 \leq N \leq 10^5)\)으로 이루어져 있다. 들판들 사이에는 \(M\)개의 양방향 길 \((0 \leq M \leq 10^5)\)이 있으며, 각각 두 들판을 연결한다.
농장에는 두 개의 축사가 있는데, 하나는 들판 1에, 다른 하나는 들판 \(N\)에 있다. 농부 존은 두 축사 사이를 몇 개의 길을 따라 걸어서 오갈 수 있도록 하고 싶다. 이를 위해 그는 최대 두 개의 새 길을 건설할 의향이 있다. 들판들의 배치 특성상, 들판 \(i\)와 \(j\) 사이에 새 길을 건설하는 비용은 \((i-j)^2\)이다.
축사 \(1\)과 \(N\)이 서로 도달 가능해지도록 하는 데 필요한 최소 비용을 구하는 것을 도와주자.
출제자: Nick Wu
채점 방식
- 테스트 케이스 2는 \(N \le 20\)을 만족한다.
- 테스트 케이스 3-5는 \(N \le 10^3\)을 만족한다.
- 테스트 케이스 6-10은 추가 제약이 없다.
출제자: Nick Wu
각 입력 테스트 케이스는 \(T\)개의 서브 케이스 (\(1\le T\le 20\))를 포함하며, 입력 케이스를 통과하려면 모두 정확히 풀어야 한다.
입력의 첫째 줄에 \(T\)가 주어지고, 이어서 \(T\)개의 서브 테스트 케이스가 주어진다.
각 서브 테스트 케이스는 두 정수 \(N\)과 \(M\)으로 시작한다. 다음 \(M\)개의 줄에 각각 두 정수 \(i\)와 \(j\)가 주어지며, 이는 서로 다른 두 들판 \(i\)와 \(j\) 사이의 길을 나타낸다. 어떤 두 들판 사이에도 길은 최대 하나이며, 모든 서브 테스트 케이스에 대한 \(N+M\)의 합이 최대 \(5 \cdot 10^5\)임이 보장된다.
\(T\)개의 줄을 출력한다. \(i\)번째 줄에는 \(i\)번째 서브 테스트 케이스의 최소 비용을 나타내는 정수를 하나 출력한다.
2
5 2
1 2
4 5
5 3
1 2
2 3
4 52
1In 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.
riseoj 작성
출처 올림피아드 > USACO > 2021-2022 > December > Silver