cho.sh물류창고
아직 제출이 없습니다시간 제한2초메모리 제한1024 MB문제
UCPC시에는 N개의 물류창고가 있으며, K개의 회사가 각 물류창고를 소유하고 있다. 물류창고에는 1번부터 N번까지 차례대로 번호가 붙어있으며, 회사 또한 1번부터 K번까지 차례대로 번호가 붙어있다. M개의 양방향 도로가 두 물류창고를 연결하고 있으며, 도로마다 물건의 이동 상한선이 정해져 있다. 두 물류창고 사이에는 여러 개의 도로가 있을 수 있으며, 임의의 두 물류창고를 연결하는 경로는 언제나 존재한다.
두 물류창고 사이에서 물건을 배송한다고 생각해 보자. 두 물류창고를 연결하는 경로상의 도로 중 가장 작은 이동 상한선이 두 물류창고의 배송 상한선이 된다. 만약 두 물류창고를 연결하는 경로가 여러 개 존재한다면, 그중에서 배송 상한선이 가장 큰 경로를 선택할 것이다.
각 회사에 대해, 해당 회사에 속한 물류창고끼리의 배송 상한선들의 총합을 구해보자.
단, 각 회사는 2개 이상의 물류창고를 소유하고 있음이 보장된다.
입력
첫 번째 줄에 물류창고의 수 N, 회사의 수 K, 도로의 수 M이 공백으로 구분되어 주어진다. (2≤N≤100 000; 1≤K≤min(2N,50 000); N−1≤M≤300 000)
두 번째 줄에는 N개의 정수 C_1, C_2, ..., C_N 가 공백으로 구분되어 주어지며, 이는 i번 물류창고를 C_i번 회사가 소유함을 나타낸다. (1≤C_i≤K)
이후 M개의 줄에 걸쳐 도로들의 정보가 주어진다. 각 줄에는 세 개의 정수 X, Y, W가 공백으로 구분되어 주어지며, 이는 X번 물류창고와 Y번 물류창고를 연결하는 이동 상한선 W의 양방향 도로를 나타낸다. (1≤X,Y≤N; 1≤W≤109)
출력
총 K개 줄에 걸쳐 1번 회사부터 K번 회사까지 각 회사에 속한 물류창고끼리의 배송 상한선들의 총합을 출력한다.