레이팅 미적용-7mm
-15mm
After Curiosity discovered not just water on Mars, but also an aggressive, bloodthirsty bunch of aliens, the Louvain-la-Neuve municipal government decided to take precautionary measures; they built shelters in order to shelter everyone in the city in the event of an extraterrestial attack.
Several alien-proof shelters have been erected throughout the city, where citizens can weather an alien invasion. However, due to municipal regulations and local building codes the shelters are limited in size. This makes it necessary for the government to assign every citizen a shelter to calmly direct themselves towards in the rare event of a fleet of UFOs blotting out the sun. Conditional on no shelter being assigned more people than it can fit, it is of the utmost importance that the time it takes until everyone has arrived at a shelter is minimized.
We model Louvain-la-Neuve as a network of \(n\) locations at which people live, connected by \(m\) bidirectional roads. Located at \(s\) points throughout the city are the shelters, each with a given maximum capacity. What is the minimum amount of time it takes for everyone to arrive at a shelter, when we assign people to shelters optimally?
The Louvain-la-Neuve municipal government has made sure that there is enough shelter capacity for its citizens and all shelters can be reached from any location, i.e. it is always possible to shelter everyone in some way.
- On the first line are three integers, the number of locations \(1 \leq n \leq 10^5\), roads \(0 \leq m \leq 2\cdot 10^5\), and shelters \(1 \leq s \leq 10\).
- Then follows a line with \(n\) integers \(0 \leq p_i \leq 10^9\), indicating the the number of people living at location \(1 \leq i \leq n\).
- Then follow \(m\) lines containing three integers \(1 \leq u, v \leq n\) and \(1 \leq w \leq 10^9\) indicating that there is a bidirectional road connecting \(u\) and \(v\) that takes \(w\) time to traverse. For any two locations there is at most one road connecting them directly, and no road connects a location to itself.
- Finally follow \(s\) lines with two integers \(1 \leq s_i \leq n\) and \(1 \leq c_i \leq 10^9\), indicating that there is a shelter with capacity \(c_i\) at location \(s_i\).
Print the minimum amount of time it takes to shelter everyone.
2 1 1
3 2
1 2 4
1 6
4
4 5 2
2 0 0 2
1 2 6
1 3 2
2 3 3
3 4 4
4 2 6
3 2
2 2
5
7 8 3
0 1 1 1 1 0 2
1 2 1
2 3 1
3 1 1
4 6 5
4 3 1
6 7 10
7 5 3
5 6 3
6 5
1 1
2 1
6
2 1 1
0 2
1 2 1000000000
2 2
0