레이팅 미적용농부 존은 최근 자신의 농장에서 여러 종류의 풀을 재배하는 실험을 하고 있다. 소마다 좋아하는 풀의 종류가 다르다는 것을 깨달았기 때문이다. 하지만 서로 다른 종류의 풀이 뒤섞여 버리는 것을 막기 위해, 서로 다른 종류의 풀은 충분히 멀리 떨어뜨려 심어야 한다.
농부 존의 농장은 \(N\)개의 밭 (\(1 \leq N \leq 200,000\))으로 이루어져 있으며, \(M\)쌍의 밭이 양방향 길로 연결되어 있다 (\(1 \leq M \leq 200,000\)). 이 길들을 이용하면 어떤 밭에서든 다른 어떤 밭으로도 이동할 수 있다. 각 길의 길이는 \(1 \ldots 1,000,000\) 범위의 정수이다. 어떤 두 밭도 최대 하나의 직접 연결된 길로만 이어져 있다.
농부 존은 처음에 각 밭에 \(K\)가지 풀 (\(1 \leq K \leq N\)) 중 하나를 심는다. 하지만 시간이 지나면서 어떤 밭의 풀을 다른 종류로 바꾸기로 결정할 수 있다. 그는 이것을 "업데이트" 연산이라고 부른다. 그는 시간에 걸쳐 여러 번의 업데이트를 수행할 수 있으며, 모든 업데이트는 누적되어 적용된다.
각 업데이트 후, 농부 존은 서로 다른 종류의 풀이 자라는 두 밭 사이의 최단 경로 길이를 알고 싶어한다. 즉, 서로 다른 종류의 풀이 자라는 모든 밭 쌍 중에서 가장 가까운 두 밭이 어디인지 알고 싶다. 이 값이 클수록 한 종류의 풀이 다른 종류의 풀과 섞이는 것을 막을 수 있으므로 이상적이다. 농장에는 항상 서로 다른 종류의 풀이 자라는 밭이 적어도 두 개 존재함이 보장된다.
입력 케이스의 30퍼센트에서는, 각 밭이 최대 10개의 길과 직접 연결되어 있다.
Problem credits: Lewin Gan
Problem credits: Lewin Gan
입력의 첫째 줄에 네 정수 \(N\), \(M\), \(K\), \(Q\)가 주어지며, \(Q\)는 업데이트의 횟수이다 (\(1 \leq Q \leq 200,000\)). 다음 \(M\)개의 줄에 길에 대한 정보가 주어진다. 각 줄은 세 정수 \(A\), \(B\), \(L\)로 이루어져 있으며, 밭 \(A\)에서 밭 \(B\)까지 (두 정수 모두 \(1 \ldots N\) 범위) 길이 \(L\)의 길이 있음을 의미한다. 다음 줄에 각 밭에서 처음 자라는 풀의 종류가 주어진다 (\(1 \ldots K\) 범위의 정수 \(N\)개). 마지막으로 \(Q\)개의 줄에 각 업데이트가 두 정수 \(A\), \(B\)로 주어지며, 밭 \(A\)의 풀을 종류 \(B\)로 바꾼다는 의미이다.
각 업데이트에 대해, 해당 업데이트가 적용된 후 서로 다른 종류의 풀이 자라는 두 밭 사이의 최단 경로 길이를 출력한다.
grass.in · 출력을 쓸 파일 grass.out3 2 3 4
1 2 3
2 3 1
1 1 2
3 3
2 3
1 2
2 21
3
3
1riseoj 작성
출처 올림피아드 > USACO > 2016-2017 > US Open > Platinum