시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 817 | 382 | 323 | 46.948% |
원빈이는 친구들과 함께 방탈출 카페에 갔다. 방탈출 카페에는 $1$번부터 $N$번까지 총 $N$개의 방이 있고, 각 방에는 친구들이 한 명씩 들어가 있다. 모든 방은 외부로부터 완전히 독립되어 있다.
방에서 탈출하지 못하는 친구들이 답답했던 원빈이는 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하려고 한다. 워프는 최대 $M$개까지 설치할 수 있는데, $i$번째 워프는 설치하는 데 $c_i$의 시간이 걸리고, 워프를 설치하면 $a_i$번 방과 $b_i$번 방 사이를 이동할 수 있다. 또한 각 방에는 출구로 바로 연결되는 비상탈출구를 설치할 수 있는데, $i$번 방에 비상탈출구를 설치하는 데 걸리는 시간은 $t_i$이다.
안타깝게도 원빈이는 머리가 나빠 워프나 비상탈출구의 설치 작업을 동시에 여럿 진행할 수 없다. 즉 한 작업이 끝나고 나서야 다음 작업을 이어서 시작할 수 있다.
원빈이를 도와 모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 구해보자.
첫 번째 줄에는 방의 개수 $N$과 설치할 수 있는 워프의 개수 $M$이 주어진다. ($2 \le N \le 200\,000$, $1 \le M \le 100\,000$)
다음 $M$개의 줄에는 워프의 정보를 나타내는 세 정수 $a_i$, $b_i$, $c_i$가 공백으로 구분되어 주어지는데, 이는 $a_i$번 방과 $b_i$번 방 사이를 잇는 워프를 설치하는 데 걸리는 시간이 $c_i$라는 의미이다. 같은 두 개의 방을 잇는 워프가 여러 개 존재할 수 있다. ($1 \le a_i, b_i \le N$, $1 \le c_i \le 10^4$, $a_i \ne b_i$)
마지막 줄에는 $N$개의 정수 $t_1$, ..., $t_n$이 주어지는데, $t_i$는 $i$번째 방에 비상탈출구를 설치하는 데 드는 시간을 의미한다. ($1 \le t_i \le 10^4$)
모든 친구들이 출구로 탈출할 수 있도록 워프와 비상탈출구를 설치하는 데 걸리는 최소 시간을 출력한다.
3 3 1 2 2 2 3 2 3 1 2 3 3 3
7
3 1 1 2 2 3 3 3
8
University > 서강대학교 > 2021 Sogang Programming Contest > Master F번
University > 서강대학교 > 2021 Sogang Programming Contest > Open F번