시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 14 3 3 23.077%

문제

현재 W국은 N개의 나라와 전쟁 중이다. W국의 전력이 월등히 우세하여 전쟁에서 승리하는 것은 시간 문제이다. W국은 첩자를 통해, N개의 나라들 중 M개의 나라만을 정복하면 나머지 나라는 자동으로 항복한다는 정보를 입수했다.

이제 M개의 나라를 적당히 골라서 정복하려고 하는데, 각 나라마다 정복하는 데 걸리는 시간이 다르다. 어떤 나라는 오래 걸리고, 어떤 나라는 매우 순식간에 정복할 수도 있다. 단 그 나라를 정복하는 데 온 전력을 집중해야 하기 때문에, 매 순간 오직 한 나라와만 전쟁을 진행할 수 있다. 우리는 최대한 빨리 M개의 나라를 정복하려고 한다.

단, N개의 나라 사이에는 속국 관계가 존재할 수 있다. 나라 A가 나라 B의 속국인 경우, 나라 B를 정복하면 나라 B의 모든 속국들이 자동으로 항복하게 된다. 속국에는 서로 계층 관계가 존재해서, 나라 A가 나라 B의 속국이고, 나라 B가 나라 C의 속국인 경우, 나라 C를 정복하면 나라 A와 나라 B 모두 자동으로 정복하는 효과를 얻는다. 즉 자신의 속국과, 속국들의 속국과, 속국들의 속국들의 속국과, . . . 이렇게 모든 하위의 나라들이 자동으로 항복하게 된다.

나라 A가 나라 B의 속국이면서 동시에 나라 C의 속국일 수 없다. 즉 속국이라면 오직 한 나라의 속국일 뿐이다. 하지만 나라 A, 나라 B, ... 등 여러 나라가 한 나라의 속국일 수는 물론 있다.

N, M이 주어지고, 속국 관계가 주어지고, 각 나라를 정복하는 데 드는 일수가 주어지면, 최대한 빨리 M개의 나라를 정복할 수 있는 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나라의 개수 N(1≤N≤200)과 M(0≤M≤N)이 주어진다. 이어서 N개의 줄에 각 나라에 대한 정보가 주어지는데, 먼저 나라의 이름이 문자열로 주어진다. 문자열의 길이는 1 이상 100 이하이며 알파벳 대소문자로 이루어져 있다. 이어서 빈 칸 뒤에 이 나라를 정복하는 데 드는 일수가 주어진다. 이어서 빈 칸이 주어지고 여러 개의 나라 이름들이 빈 칸을 사이에 두고 주어질 수가 있는데, 이 뒤에 주어지는 나라들이 바로 현재 나라의 속국들이 된다.

출력

첫째 줄에 M개의 나라를 최대한 빨리 정복하려고 할 때 며칠이 걸리는지 출력한다.

예제 입력

3 2
CountryA 10
CountryB 20 CountryA
CountryC 15

예제 출력

20

힌트

CountryB만 정복하면 자동으로 CountryB의 속국인 CountryA가 정복되어 2개 나라를 정복할 수 있다.

출처

ACM-ICPC > Regionals > Asia > Iran > Tehran Site 2006 G번

  • 문제를 번역한 사람: author5