Informatica Online Judge

  장비를 정지합니다 [1754 / 06DA]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 1   Total Tried : 2


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[2016 나는코더다 송년 대회 (Polish Collegiate Programming Contest 2012)]

Background

졸업논문을 완성하지 못한 형서는 학교에 대한 테러 계획을 세웠다. 고급정보과학 시간에 몰래 형서가 제작한 기계는, 전원을 켠 순간부터 폭주하기 시작해서 온 학교를 쑥대밭으로 만들고 있다. 으악!

학교를 살려내기 위해서, 박종화 선생님은 형서의 설계도를 입수했다. 설계도에 의하면, 폭주 기계에는 $n$개의 장비가 존재하며, 현재 1번 장비만이 폭주하고 있다. 장비를 정지시키기 위해서는, 박종화 선생님이 각각의 장비에 전기 충격을 가해야 한다.

설계도에 의하면, 전기 충격에는 약한 충격강한 충격이 있다. $i$번 장비에 약한 충격을 가하는 데는 $u_i$ 와트의 전력이 필요하며, 강한 충격을 가하는 데는 $z_i$ 와트의 전력이 필요하다. ($u_i < z_i$) 약한 충격과 강한 충격 모두 $i$번 장비를 정지시키지만, 약한 충격을 받았을 때는, $r_i$ 개의 특정한 장비들이 다시 작동을 시작하게 된다! 각각의 장비에 대해서, 이러한 특정한 장비들은 $g_{i, 1}, ..., g_{i, r_i}$ 와 같은 리스트로 표현 가능하며, 이 리스트 역시 설계도에 적혀 있다.

박종화 선생님은 모든 장비를 정지하려고 한다. 하지만, 학교는 난장판이 되었고, 공급받을 수 있는 전력량에는 한계가 있다. 박종화 선생님은 전기 충격에 사용한 전력의 합의 최솟값을 구하려고 한다. 힘을 합쳐서 박종화 선생님을 도와드리자.

Input

첫번째 줄에는 장비의 개수를 뜻하는 정수 $n$이 주어진다. ($1 <= n <= 200,000$).

이후 $n$개의 줄에 장비의 정보가 순서대로 주어진다. 이 중 $i$번째 줄은 장비 $i$의 정보를 나타낸다. 각각의 줄에는 먼저 세 정수 $u_i$, $z_i$, $r_i$ 가 주어지며 ($1 <= u_i < z_i <= 10^9$, $1 <= r_i < n$), 이후 $r_i$개의 정수 $g_{i, 1}, ..., g_{i, r_i}$ ($1 <= g_{i, j} <= n$)가 주어진다. 모든 $i$에 대해 $r_i$의 합은 $10^6$을 넘지 않는다. 다시 작동을 시작하는 장비의 리스트에, 같은 원소가 여러 번 등장할 수 있으며, 이 때는 해당 장비를 등장 횟수만큼 종료해야 한다.

Output

모든 장비를 정지하기 위해 필요한 전력량의 최솟값을 출력하라.

IO Example

입력
4
4 27 3 2 3 2
3 5 1 2
1 13 2 4 2
5 6 1 2

출력
26

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]