USACO 2017 US Open Contest, Gold 2. Switch Grass- 식물원 > 문제은행 : 정보올림피아드&알고리즘




3069 : 식물원

제한시간
2000 ms   
메모리제한
512 MB   
해결횟수
0 회   
시도횟수
12 회   

문제

유명한 식물원 중에 하나인 KOI식물원의 연구원인 범준이는 최근 식물원에 여러 종류의 허브를 재배하며 실험하게 되었다. 

허브를 심을 때는 주의할 점이 있는데 서로 다른 종류의 허브 사이에는 종의 보존과 안정된 성장을 위하여 최소한의 여유간격이 필요하다고 한다.

 

KOI식물원은 N(1 <= N <= 200,000)개의 필드와 필드 사이를 양방향으로 연결하는 M(1 <= M <= 200,000)개의 통로가 있다. 

이 통로들을 이용하면 어느 필드에서든 다른 임의의 특정 필드로 이동할 수 있다. 

한 통로의 길이는 1 ~ 1,000,000 이고 임의의 두 필드를 직접 연결하는 통로의 개수는 많아야 한 개뿐이다.

 

범준이는 초기에 K(1<=K<=N)종류의 허브를 심는다. 하지만 시간이 지나면서 한 필드의 허브를 다른 종류로 바꾸어 재배할 수도 있다. 

이 과정을 범준이는 “업뎃”이라고 부른다. 그리고 업뎃은 누적되어 적용된다.

 

범준이는 종의 보존과 안정된 성장을 위하여 각각의 업뎃 이후 서로 다른 종류의 허브간 거리 중에 최소값이 얼마인지 알고자 한다. 

이 값이 클수록 종의 보존과 안정된 성장에 유리하기 때문이다.


식물원에는 적어도 2종류 이상의 서로 다른 허브가 있다는 것이 보장된다고 한다.

 

입력 데이터의 30%는 각 필드에 연결된 통로의 개수가 많아야 10개이다. 

 


입력형식

첫 행에 N, M, K, Q(1<=Q<=200,000))가 공백으로 구분하여 주어진다. 각각 필드의 수, 통로의 수, 초기 허브 종류 수, 업뎃 수를 의미한다. 이후 M개의 행에 통로에 대한 정보 A, B, L이 공백을 구분하여 주어진다. A필드와 B필드의 거리가 L이라는 의미이다. 다음 행에 N개의 수가 주어지는데 각 필드에 심은 허브 종류 번호이다. 이후 Q개의 행에 X, Y두 수가 공백으로 구분하여 주어지는데 X번 필드의 허브 종류를 Y로 바꾼다는 의미이다.

출력형식

각 업뎃에 대하여 서로 다른 종류의 허브간 거리 중에 최소값이 얼마인지 행으로 구분하여 출력한다.

입력 예

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