| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 58 | 19 | 17 | 32.075% |
Albert는 무방향 그래프에서 경로 찾는 게임을 즐겨한다. 다만 주어진 그래프에서 최단 경로를 찾는것은 재미가 없으므로, 현재 그래프에 새로운 간선을 추가하거나 혹은 이전에 추가했던 간선을 삭제하며 계속 그래프를 바꿔가며 최단 경로를 찾는 게임을 고안했다.
처음에 정점이 $N$개이고 간선이 $M$개인 그래프 $G$을 만드는데, 정점은 $1, 2, \dots, N$ 으로 번호가 붙어있다. $i$번째 간선은 $(X_i, Y_i, C_i)$로 표현하는데 정점 $X_i, Y_i$를 잇고 가중치가 $C_i$임을 나타낸다. 예를 들어 아래 그림은 $N = 6$, $M = 5$, $X = [1, 2, 1, 4, 5]$, $Y = [2, 3, 4, 3, 6]$, $C = [8, 7, 10, 2, 4]$ 인 그래프를 보여준다. 간선에 방향성이 없음에 유의하자. 두 정점을 연결하는 간선이 여럿 있을 수 있지만 (예제 참고) 모든 간선은 $X_i \ne Y_i$를 만족한다.
이렇게 처음에 사용할 그래프 $G$을 만든 후, 총 $Q$개의 연산을 수행하는데, 연산에는 3가지 종류가 있다. $k$번째 연산의 종류는 $R_k \in \{1, 2, 3\}$ 으로 표현하자.
다만 $A_k, B_k, W_k$는 $R_k = 2$인 경우에만 정의되므로 편의상 $R_k \ne 2$인 경우엔 $A_k = B_k = W_k = 0$이라 하자.
예를 들어 위 예제의 그래프에 $Q = 9$ 개의 연산을 적용한다고 하고, 연산의 종류는 $R = [1, 2, 1, 2, 1, 3, 1, 3, 1]$, 그리고 $A = [0, 3, 0, 2, 0, 0, 0, 0, 0]$, $B = [0, 5, 0, 6, 0, 0, 0, 0, 0]$, $W = [0, 1, 0, 2, 0, 0, 0, 0, 0]$라 하자.
52 118 99 118 52"가 순서대로 적혀있다.입력으로 $N, M, Q$, $X, Y, C$ 그리고 $R, A, B$가 주어졌을 때 1번 연산에서 구한 점수들을 순서대로 구해보자 -- Albert는 당신의 도움을 받아 자신의 답이 맞는지 확인해보고싶다.
첫 줄에 테스트 케이스의 수 $T$가 주어진다.
각 테스트 케이스의 첫 줄에는 $N, M, Q$가 공백으로 구분되어 주어진다. 다음 $M$줄에 걸쳐 $i$번째 줄에 3개의 정수인 $X_i, Y_i, C_i$가 주어진다. 다음 $Q$줄에 걸쳐 $k$번째 줄에 $k$번째 연산의 종류와, 2번 연산인 경우 추가로 필요한 정보가 주어진다. 각 줄의 첫 정수는 $R_k$로 연산의 종류를 나타낸다. $R_k = 2$인 경우에 한해서만 같은 줄에 3개의 정수가 더 주어지는데 이는 $A_k, B_k, W_k$이다.
각 테스트 케이스의 정답인 그래프의 점수들을 공백으로 구분하여 각 줄에 출력한다.
4 6 5 9 1 2 8 2 3 7 1 4 10 4 3 2 5 6 4 1 2 3 5 1 1 2 2 6 2 1 3 1 3 1 4 1 16 1 2 10 1 2 1 2 100 1 2 3 4 10 1 2 2 3 20 1 2 2 3 5 2 1 2 5 1 3 1 3 1 3 1 4 1 5 1 2 10 2 1 2 100 3 1 3 1 4 1 11 1 2 10 1 2 1 2 5 1 2 2 1 1 1 3 1 3 1 3 1
52 118 99 118 52 10 10 20 140 65 80 140 20 10 10 10 5 1 5 10 10
예제 1: 본문에서 다루었다.
예제 2: 처음의 그래프는 아래 그림처럼 간선이 1개인 그래프이다.
이후 간선이 추가될 때 마다 아래 그림처럼 그래프가 바뀐다. 이 때 두 정점을 잇는 간선이 여럿일 수 있음에 유의하자.
예제 3: 처음의 그래프는 2번 예제의 그래프와 같다.
예제 4: 추가 설명 없음.
© 2026 주식회사 데이원컴퍼니. All Rights Reserved.