JOI 2016 본선, 2018camp contest3 problemE- 4딸라 > 문제은행 : 정보올림피아드&알고리즘




3157 : 4딸라

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

문제

JOI 나라는 N개의 도시로 이루어져 있다. 각 도시는 1번부터 N번까지 번호가 매겨져 있고, 1번 도시가 수도이다.

 

이 나라는 철도 회사가 하나이고, 이 회사가 M개의 노선을 운행하고 있다. 이 노선에는 각각 1부터 M까지 번호가 매겨져 있으며, i번째 노선은 도시 Ui와 도시 Vi를 양방향으로 잇는다. 도시와 도시 사이는 철도 이외의 수단으로 이동할 수 없다. 또 어느 도시에서 어느 도시도 철도를 1회 이상 이용해 이동할 수 있다.

 

현재 모든 노선의 요금은 1달러이다. 철도 회사가 연이은 적자로 파산 직전이기 때문에, 일부 노선의 요금을 4달러로 올리려고 한다. 이들을 한 번에 인상할 경우 반발이 심하기 때문에 1년에 한 노선씩 Q년 동안 인상하려 한다. 다시 말하면, j년 째(1≤j≤Q)에는 Rj(1≤Rj≤M)번째 노선의 요금을 4달러로 올릴 계획이다. 한번 인상된 요금은 계속 유지된다. 같은 노선을 두 번 인상하는 일은 없다.

 

한편 철도 회사에서는 매년 만족도 조사를 실시한다. 만족도 조사는 매년 말에 실시하므로 j년째 만족도 조사는 노선 Rj의 요금이 인상된 후 실시한다. 만족도 조사에서는 다음 조건이 참인 사람들이 불만족이라고 답한다.

 

요금 인상 계획 전에 1번 도시로 가는 최소 비용보다, 지금 1번 도시로 가는 최소 비용이 더 비싸다.

여기서 "요금 인상 계획 전"​은 JOI 나라의 첫 요금 인상 전이다.

 

철도는 환승이 되지 않기 때문에, 어떤 경로의 비용은 그 경로에 있는 노선 요금의 합이다.

 

1번 도시에 사는 사람은 절대 불만족하지 않는다.

 

앞으로 Q년 동안 요금 인상 계획이 주어졌을 때, 만족도 조사에서 불만족하는 사람이 있는 도시의 수를 찾는 프로그램을 작성하여라. ​ 


입력형식

첫째 줄에 N,M,Q가 공백을 사이에 두고 주어진다. 각각 도시의 수, 노선의 수, 요금 인상 계획의 년 수를 뜻한다. 다음 M개의 줄 중 i번째 줄에는 i번째 노선이 잇는 도시를 나타내는 두 정수 Ui, Vi가 주어진다. 다음 Q개의 줄 중 j번째 줄에는 j번째 년에 인상되는 노선 번호인 Rj가 주어진다. 입력 데이터는 다음 조건을 만족한다. 2≤N≤100,000 1≤Q≤M≤200,000 1≤Ui≤N (1≤i≤M) 1≤Vi≤N (1≤i≤M) Ui≠Vi (1≤i≤M) 1≤Rj≤ M (1≤j≤Q) Rj≠Rk (1 ≤ j < k ≤ Q) 어떤 두 도시도 그들을 직접 잇는 노선은 1개 이하이다. 어떤 도시에서도 1번 도시로 갈 수 있다.

출력형식

Q개의 줄에 거쳐 출력한다. j번째 줄에는 j년째 만족도 조사에서 불만족한 사람이 있는 도시의 수를 출력한다.

부분 문제 

부분 문제 1 [14점] 다음 조건을 만족한다. N≤100 M≤4,950 Q≤30 

부분 문제 2 [14점] Q≤30 

부분 문제 3 [40점] Q개의 출력하는 수 중 서로 다른 것은 50가지를 넘지 않는다. 

부분 문제 4 [32점] 추가 제한 없음.


입력 예

5 6 5
1 2
1 3
4 2
3 2
2 5
5 3
5
2
4
1
3

출력 예

0
2
2
4
4


경기도 안양시 동안구 평촌대로 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