레이팅 미적용베시는 \(1\ldots N\)으로 번호가 붙은 정점 \(N\)개(\(2\le N\le 10^5\))와 \(1\ldots 2N\)으로 번호가 붙은 포털 \(2N\)개로 이루어진 네트워크 안에 있다. 각 포털은 서로 다른 두 정점 \(u\)와 \(v\) (\(u\neq v\))를 연결한다. 여러 포털이 같은 정점 쌍을 연결할 수도 있다.
각 정점 \(v\)는 서로 다른 포털 4개와 인접해 있다. \(v\)에 인접한 포털의 목록은 \(p_v=[p_{v,1},p_{v,2},p_{v,3},p_{v,4}]\)로 주어진다.
현재 위치는 순서쌍 \((\text{현재 정점}, \text{현재 포털})\), 즉 \(1\le v \le N\), \(1\le i\le 4\)인 쌍 \((v,p_{v,i})\)로 표현할 수 있다. 현재 위치를 바꾸기 위해 다음 두 연산 중 하나를 사용할 수 있다:
- 현재 포털을 통해 이동하여 현재 정점을 바꾼다.
- 현재 포털을 전환한다. 각 정점에서 목록의 앞 두 포털이 서로 짝을 이루고, 뒤 두 포털도 서로 짝을 이룬다. 즉, 현재 위치가 \((v,p_{v,2})\)라면 포털 \((v,p_{v,1})\)로 전환할 수 있고, 그 반대도 가능하다. 마찬가지로 현재 위치가 \((v,p_{v,3})\)이라면 포털 \((v,p_{v,4})\)로 전환할 수 있고 그 반대도 가능하다. 다른 전환은 허용되지 않는다 (예를 들어 포털 \(p_{v,2}\)에서 포털 \(p_{v,4}\)로 전환할 수 없다).
전체 위치는 총 \(4N\)개이다. 안타깝게도 모든 위치가 연산의 나열을 통해 다른 모든 위치에서 도달 가능하지는 않을 수 있다. 그래서 \(c_v\) (\(1\le c_v\le 1000\)) 무니의 비용을 내면 \(v\)에 인접한 포털 목록을 원하는 순서로 재배열할 수 있다. 재배열 후에는 목록의 앞 두 포털이 서로 짝을 이루고, 뒤 두 포털도 서로 짝을 이룬다.
예를 들어 \(v\)에 인접한 포털들을 \([p_{v,3},p_{v,1},p_{v,2},p_{v,4}]\) 순서로 재배열하면, 정점 \(v\)에 있을 때 다음이 성립한다.
- 현재 포털이 \(p_{v,1}\)이면 포털 \(p_{v,3}\)으로 전환할 수 있고, 그 반대도 가능하다.
- 현재 포털이 \(p_{v,2}\)이면 포털 \(p_{v,4}\)로 전환할 수 있고, 그 반대도 가능하다.
- 더 이상 포털 \(p_{v,1}\)에서 \(p_{v,2}\)로, 또는 포털 \(p_{v,3}\)에서 포털 \(p_{v,4}\)로 (또는 그 반대로) 전환할 수 없다.
모든 가능한 위치에서 다른 모든 위치로 도달할 수 있도록 네트워크를 수정하는 데 필요한 무니의 최소 총합을 계산하라. 테스트 데이터는 네트워크를 수정하는 유효한 방법이 적어도 하나 존재하도록 구성되어 있음이 보장된다.
문제 제공: Benjamin Qi
채점 방식
- 테스트 케이스 2-4에서는 모든 \(v\)에 대해 \(c_v=1\)이다.
- 테스트 케이스 5-12는 추가 제약이 없다.
문제 제공: Benjamin Qi
첫째 줄에 \(N\)이 주어진다.
다음 \(N\)개의 줄에는 각각 하나의 정점에 대한 설명이 주어진다. \(v+1\)번째 줄에는 공백으로 구분된 다섯 정수 \(c_v,p_{v,1},p_{v,2},p_{v,3},p_{v,4}\)가 주어진다.
각 \(v\)에 대해 \(p_{v,1},p_{v,2},p_{v,3},p_{v,4}\)는 모두 서로 다르고, 모든 포털은 정확히 두 정점의 인접 목록에 나타남이 보장된다.
모든 가능한 위치에서 다른 모든 위치로 도달할 수 있도록 네트워크를 수정하는 데 필요한 무니의 최소 총합을 한 줄에 출력한다.
5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 513It suffices to permute the adjacency lists of vertices \(1\) and \(4\). This
requires a total of \(c_1+c_4=13\) moonies. We can let \(p_1=[1,9,4,8]\) and
\(p_4=[7,4,6,3]\).