레이팅 미적용Anna has been tasked with designing the wiring for a new offshore wind farm in the North Sea consisting of \(N\) turbines, numbered \(0, 1, \ldots, N-1\). Her goal is to ensure that all turbines are connected to the shore as cheaply as possible.
Anna has a list of \(M\) potential connections, each linking two wind turbines and having a specific cost. Additionally, the nearby city has agreed to cover the costs of connecting a consecutive interval \([\ell, r]\) of turbines to the shore. That is, each turbine \(t\) in this range (\(\ell\le t\le r\)) is directly connected to the shore for free. If all potential connections are built, there is a way to reach any wind turbine from any other wind turbine. That implies that as soon as one of the wind turbines is connected to the shore, it is possible to build connections such that the power from all the turbines can be transferred to the shore. Of course, more connections to the shore may allow for a cheaper total cost. Note that the free connections are the only direct ones to the shore.
It is Anna's job to select a subset of the potential connections in a way that minimizes the sum of their costs, while ensuring that every wind turbine can reach the shore (possibly via other wind turbines).
In order to make an informed decision, the city provides Anna with \(Q\) possible options for the interval \([\ell, r]\). The city asks Anna to compute the minimum cost for each of these scenarios.
(An illustrative figure from the official statement is omitted here.)
- \(2 \le N\le 100\,000\).
- \(1 \le M\le 100\,000\).
- \(1 \le Q\le 200\,000\).
- \(0 \le u_i,v_i \le N-1\).
- \(u_i \ne v_i\), and there is at most one direct connection between each pair of wind turbines.
- \(1 \le c_i \le 1\,000\,000\,000\).
- \(0 \le \ell_i\le r_i \le N-1\).
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group, you need to solve all the test cases in the test group.
Group | Score | Limits 1 | 8 | \(M=N-1\) and the \(i\)th connection has \(u_i=i\) and \(v_i=i+1\), i.e. if all connections are built, they form a path \(0 \leftrightarrow 1 \leftrightarrow 2 \leftrightarrow \ldots \leftrightarrow N-1\) 2 | 11 | \(N,M,Q\le 2\,000\) and \(\sum(r_i-\ell_i+1) \le 2\,000\) 3 | 13 | \(r_i=\ell_i+1\) for all \(i\) 4 | 17 | \(1\le c_i \le 2\) for all \(i\), i.e., each connection has cost either \(1\) or \(2\) 5 | 16 | \(\sum(r_i-\ell_i+1)\le 400\,000\) 6 | 14 | \(\ell_i=0\) for all \(i\) 7 | 21 | No additional constraints
The first line of the input contains three integers, \(N\), \(M\) and \(Q\).
The following \(M\) lines contain three integers each, \(u_i\), \(v_i\) and \(c_i\). The \(i\)th line describes a potential connection between wind turbines \(u_i\) and \(v_i\) that has the cost \(c_i\). These connections are undirected and connect two different turbines. No two connections are between the same pair of turbines. It is guaranteed that, if all potential connections are built, any wind turbine is reachable from any other (directly or indirectly).
The next \(Q\) lines contain two integers each, \(\ell_i\) and \(r_i\), describing the scenario where the shore directly connects to the wind turbines \(\ell_i,\ell_i+1,\ldots,r_i\). Note that we can have \(r_i = \ell_i\) when the shore directly connects to a single wind turbine.
Output \(Q\) lines, one line per scenario, containing one integer each, the minimum cost of connecting the turbines such that every turbine can deliver its power to the shore.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Subtask 1 | 8점 | None |
Subtask 2 | 11점 | None |
Subtask 3 | 13점 | None |
Subtask 4 | 17점 | None |
Subtask 5 | 16점 | None |
Subtask 6 | 14점 | None |
Subtask 7 | 21점 | None |
5 5 3
1 0 2
0 2 5
1 2 3
3 0 6
2 4 3
1 1
3 4
1 4
14
8
2
5 4 4
0 1 3
1 2 1
2 3 5
3 4 2
0 4
2 3
2 4
2 2
0
6
4
11
7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 1
2 3
4 5
5 6
12
10
10
10
7 7 3
2 6 1
1 0 1
0 5 1
1 2 2
3 4 1
5 3 1
5 4 1
5 6
1 3
3 4
5
4
6
7 7 4
6 4 3
1 4 5
3 2 4
0 3 2
5 2 3
4 0 1
1 3 1
0 3
0 6
0 1
0 4
7
0
12
6
9 13 4
0 1 1
2 0 3
1 2 4
5 4 4
2 5 6
3 1 7
8 1 4
6 3 9
0 3 5
3 5 3
4 3 2
6 2 4
7 8 5
1 8
4 7
6 7
1 2
1
14
22
24
6 5 1
0 1 1000000000
1 2 1000000000
2 3 1000000000
3 4 1000000000
4 5 1000000000
1 1
5000000000