| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2.5 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 489 | 166 | 134 | 35.450% |
2025년, 신촌의 다섯 대학교인 서강대, 숙명여대, 연세대, 이화여대, 홍익대는 신촌에서 원활하게 통행하기 위한 도로망을 구축하고 관리하기로 결정하였다. 신촌은 $N$개의 정점으로 이루어져 있고, 그 위에 서로 다른 두 정점을 연결하는 방향 없는 도로를 $M$개 건설하였다. 임의의 두 정점을 직접적으로 잇는 도로는 최대 한 개만 존재하고, 어떤 두 정점을 선택하더라도 그 두 정점을 연결하는 경로가 존재함이 보장된다.
각 도로는 다섯 학교 중 한 학교가 담당하여 관리한다. 도로를 관리하는 데에는 매년 관리비가 필요한데, 어떤 도로의 관리비는 그 도로를 관리하는 학교에 따라 결정된다. 즉, 서강대가 관리하는 도로는 모두 관리비가 동일하며, 이는 다른 학교 또한 마찬가지이다.
그런데, 2125년부터 각 학교의 예산이 부족해져 관리비가 유동적으로 바뀌게 되었다. 그래서 다섯 학교는 어떤 두 정점을 선택하더라도 관리된 도로만을 사용해 그 두 정점을 연결하는 경로가 존재하도록 도로를 관리하고, 나머지 도로는 한 해 동안 관리하지 않기로 합의하였다. 이제 여러분은 매년 각 학교의 도로 관리비를 입력받아, 합의한 대로 도로를 관리하기 위한 관리비의 합의 최솟값을 출력해야 한다. 다섯 대학교가 비용을 절약할 수 있도록 도와주자.
첫 번째 줄에 정점의 개수 $N$과 도로의 개수 $M,ドル 관리비가 바뀌는 횟수 $Q$가 공백으로 분리되어 주어진다. $(1 \le N \le 5 \times 10^4;$ $N-1 \le M \le 10^5;$ 1ドル \le Q \le 2 \times 10^4)$
두 번째 줄부터 $M$개의 줄에 걸쳐 도로에 대한 정보가 주어진다. 그중 $i$번째 줄에는 $i$번째 도로가 연결하는 두 정점 $u_i,ドル $v_i$와 도로를 관리하는 학교를 나타내는 문자 $z_i$가 공백으로 구분되어 주어진다. $(1 \le u_i,v_i \le N;$ $u_i \neq v_i;$ $z_i \in \{$A,B,C,D,E$\})$ A,B,C,D,E 는 각각 서강대, 숙명여대, 연세대, 이화여대, 홍익대에 해당한다.
$M+2$번째 줄부터 $Q$개의 줄에 걸쳐 새롭게 정해진 각 학교의 도로 관리비 $a_j,ドル $b_j,ドル $c_j,ドル $d_j,ドル $e_j$가 공백으로 구분되어 주어진다. $(0 \le a_j,b_j,c_j,d_j,e_j \le 10^7)$ 이는 순서대로 서강대, 숙명여대, 연세대, 이화여대, 홍익대의 도로 관리비에 해당한다.
임의의 두 정점을 직접적으로 잇는 도로는 최대 한 개만 존재하고, 어떤 두 정점을 선택하더라도 그 두 정점을 연결하는 경로가 존재함이 보장된다.
$Q$번의 도로 관리비 변동에 대하여, 각각 관리비 변경 후 관리비 합의 최솟값을 새로운 줄에 출력한다.
6 9 3 1 2 E 1 3 C 2 3 A 3 6 D 2 4 B 2 5 D 3 5 B 4 5 C 5 6 A 10 3 4 9 8 2 4 4 2 1 0 2 0 2 4
23 11 2
예제 입력에서 신촌의 도로망 구조는 아래와 같다. 각 도로는 관리하는 학교의 상징색으로 칠해져 있으며, 가독성을 위해 학교의 로고가 도로 위에 그려져 있다.
각 순서쌍에 따라 도로별 관리비를 변경할 때, 변경 후 관리비 합의 최솟값은 각각 23ドル,ドル 11ドル,ドル 2ドル$가 된다. 관리비의 합을 최소화하기 위해 관리하기로 결정한 도로들이 아래 그림에 강조되어 있다. 단, 관리비의 합을 최소화하기 위해 도로를 선택하는 방법은 유일하지 않을 수 있음에 유의하자.