USACO 2017 Open Contest Platinum #2(Problem Credit: Lewin Gan)- 교역 > 문제은행 : 정보올림피아드&알고리즘




4479 : 교역

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

문제

정올국에는 N개의 지역(/)이 있고, 각 지역마다 생산하는 특산물이 다르다.

또한 정올국에는 두 지역을 잇는 M개의 도로가 있다. 각 도로의 길이(거리)는 각각 다르다. 도로는 항상 양방향 통행 가능하다.

 

각 지역은 항상 한가지의 특산물만 생산한다.

그러므로 그 외의 다른 특산물을 얻기 위해서는 다른 지역과 교역(지방끼리의 무역)을 해야 한다.

당연히 교역은 서로 다른 특산물을 생산하는 지역끼리만 시행하게 된다.

두 지역에서 생산하는 특산물이 서로 다르다면, 두 지역은 항상 교역이 가능하다.

두 지역이 서로 교역을 하게 된다면, 교역 경로는 항상 두 지역간의 최단경로로만 이루어진다.

따라서 정올국에서 가장 활발히 교역하는 두 지역은, 서로 다른 특산물을 생산하면서 두 지역간의 최단 거리가 가장 짧은 두 지역이다.

 

정올국의 대통령인 상준이는 가장 활발히 교역하는 두 지역간의 최단 거리가 궁금해졌다.

사실 이를 구하는 것은 어렵지 않다.

문제는 어떤 지역은 시간이 흐름에 따라 생산하는 특산물을 바꾸기도 한다는 것이다.

그 순간 가장 활발히 교역하는 두 지역간의 최단 거리 역시 바뀔 수 있다.

 

따라서 상준이는 이에 대비한 프로그램을 만드는 것을 정보왕인 당신에게 부탁하기로 하였다.

시간 순서대로, 어떤 지역에서 생산하는 특산물이 바뀔 때마다, 가장 활발히 교역하는 두 지역간의 최단거리를 출력해 주는 프로그램을 작성하라.

 

 


입력형식

첫 줄에 N, M, K, Q가 공백을 사이에 두고 주어진다.

N은 정올국에 존재하는 지역의 개수, M은 도로의 개수, K는 총 특산품의 종류, Q는 어떤 지역의 특산품이 변경되는 횟수이다.

 

다음 M줄에 걸쳐서, u, v, d가 각각 공백을 사이에 두고 주어진다. 이는 지역 u에서 지역 v를 직접적으로 잇는 거리 d의 양방향 도로가 존재함을 뜻한다.

다음 한 줄에, N개의 정수 ai가 공백을 사이에 두고 주어진다. 이는 각 지역에서 생산되는 특산품의 종류를 뜻한다.

다음 Q줄에 걸쳐서, 시간 순서대로, A B가 주어진다. 이는 지역 A의 특산물이 B로 변경됨을 뜻한다. 

 

 

부분문제의 제약 형식

 

모든 부분문제에서 1≤N≤200,000, 1≤M≤200,000, 1≤K,ai≤N, 1≤u,v≤N, 1≤d≤106, 1≤Q≤200,000, 1≤A≤N, 1≤B≤K를 만족한다. 모든 입력값은 정수이다.

 

부분문제 1) (30점) 모든 지역에 있어서, 그 지역과 직접적으로 연결된 도로는 많아야 10개 이하이다.

부분문제 2) (70점) 주어진 제약조건 외에 아무 제약조건이 없다.​ 


출력형식

Q개의 줄에 걸쳐서, 특산품 변화가 있을 때마다의 가장 활발히 교역하는 두 지역간의 최단 거리를 출력한다. 

어떤 상황이든, 모든 지역이 같은 특산품을 생산하는 경우는 없다는 것을 보장한다.


입력 예

3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 2

출력 예

1
3
3
1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP