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년 동안 요금 인상 계획이 주어졌을 때, 만족도 조사에서 불만족하는 사람이 있는 도시의 수를 찾는 프로그램을 작성하여라.
입력형식
출력형식
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 |