시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
8 초 | 1024 MB | 19 | 7 | 7 | 38.889% |
You have a 2D array A of size $N \times N$. Each cell initially contains 0.
You are also given Q queries of the form X1 X2 Y1 Y2 W, which means you should perform the following operation on A:
Consider an undirected graph G with N vertices. For each 1 ≤ i, j ≤ N, there is an edge connecting vertices i and j with cost A[i][j]. Calculate the cost of Minimum Spanning Tree of G.
The first line contains a single integer N, Q.
The next Q lines contain five integers X1 X2 Y1 Y2 W, describing a query.
Print the cost of Minimum Spanning Tree of G.
5 3 1 1 2 4 10 2 2 3 4 10 3 3 4 4 10
0
5 5 3 3 4 5 -10 1 2 3 4 20 4 4 5 5 -10 2 2 4 4 -20 1 1 2 4 0
-20
6 8 1 3 6 6 3 4 4 6 6 10 3 3 5 6 -8 1 2 5 5 -7 1 2 6 6 -1 1 3 4 5 6 3 5 6 6 7 2 3 6 6 3
-2