순찰 구역 관리 > 문제은행



실전대비 Level8

1787 : 순찰 구역 관리

제한시간: 1000 ms    메모리제한: 256 MB
해결횟수: 2 회    시도횟수: 6 회   



한 도시의 경찰서에서 관리하는 순찰 구역들은 덤불로 분리되어 있고, 1부터 N(1≤N≤200)까지 연속적으로 번호가 붙어 있다. 

이 도시의 경찰관들은 N개의 순찰지역을 자유롭게 이동하기를 원한다. 

경찰관들은 임의의 순찰 구역으로부터 다른 모든 순찰 구역으로 이동할 수 있도록 순찰 구역 쌍들 사이의 샛길들을 관리하기를 원한다.

경찰관들은 그들이 관리하고 있는 샛길을 따라 양방향으로 이동할 수 있다.

 

경찰관들은 실제로 샛길을 처음부터 새로 만들지 않고, 

대신에 그들이 발견한 범죄자들이 만들어 놓은 샛길을 관리함으로써 이동하는데 사용한다. 

매주 그들은 이미 발견한 범죄자들이 만든 샛길들의 일부나 전부를 선택하여 관리할 수 있다. 

신기하게도 경찰관들은 매주 초에 범죄자들이 만들어 놓은 새로운 샛길을 하나씩 발견한다. 

그리고 나서 그들은 임의의 순찰 구역에서 다른 순찰 구역으로 이동할 수 있도록 그 주 동안 관리할 샛길들의 집합을 결정해야 한다. 

경찰관들은 현재 그들이 관리하고 있는 샛길들만을 이용할 수 있다.

이와 함께 경찰관들은 항상 그들이 관리해야 하는 샛길의 총 길이를 최소화하기 원한다.

경찰관들이 샛길을 관리하는데 드는 비용은 샛길의 길이에 비례한다. 

전번 주에 어떤 샛길을 관리했든지 상관없이, 

경찰관은 그들이 이미 발견한 범죄자들의 샛길 집합에 임의의 부분 집합을 선택해서 관리할 수 있다.

 

범죄자들의 샛길은 결코 직선이 아니다. 같은 두 순찰 구역을 잇는 두 샛길의 길이가 서로 다를 수도 있다. 

더구나 두 샛길이 교차하더라고, 경찰들은 지침에 따라, 순찰 구역에서가 아니면 샛길을 바꾸어 이동하지 않는다. 

매주 초에 경찰관들은 그들이 새로 발견한 범죄자의 샛길 하나를 알려줄 것이다. 

그러면 당신의 프로그램은 경찰관들이 임의의 순찰 구역에서 다른 모든 순찰 구역으로 이동할 수 있도록 

그들이 그 주에 관리해야 할 샛길들의 최소 총 길이를 출력해야 한다. 

만약 그런 샛길들이 존재하지 않는다면 존재하지 않는다는 표기를 해야 한다.

 




첫째 줄에는 두 정수 N(기준 순찰 구역)과 W가 빈칸을 사이에 두고 주어진다.

W(1≤W<6,000)는 프로그램이 처리해야 할 주(week)의 수이다. W만큼 매주 발견된 범죄자들의 샛길에 대한 정보가 한 줄로 주어진다. 이 줄에는 세정수가 빈칸을 사이에 두고 주어진다. 양 끝점(두 순찰 구역의 번호)과 샛길의 길이(1 이상 10,000이하인 정수), 어떤 범죄자의 샛길도 양끝 점으로 같은 순찰 구역을 갖지 않는다.




새로 발견된 범죄자의 오솔길 하나가 입력되는 즉시 당신의 프로그램은 경찰관들이 임의의 순찰 구역에서 다른 순찰 구역으로 이동할 수 있도록 그들이 관리해야 하는 샛길들의 최소 총 길이를 한 줄에 출력해야 한다. 만일 현재까지 주어진 샛길들을 가지고 경찰관들이 임의의 순찰 구역에서 다른 순찰 구역으로 이동할 수 없다면 -1을 출력한다.

문제의 이해를 돕기 위해 위의 입력과 출력을 설명하면 4라는 순찰 구역을 기준으로 6주 동안의 새로운 샛길 정보가 들어오면 각 주마다의 순찰 구역의 최소 길이를 출력한다.
새로 들어온 순찰 구역으로 연결되는 길이 없을 때는 -1을 출력한다.



4 6
1 2 10
1 3 8
3 2 3
1 4 3
1 3 6
2 1 2
-1
-1
-1
14
12
8






HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.