{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:35.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/a930e7b72817c8a4a42d0ab45d7538d1?v\u003d1715796024\" alt\u003d\"/problems/incaseofinvasion/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003e\n \u003cp\u003eAfter Curiosity discovered not just water on Mars, but also\n an aggressive, bloodthirsty bunch of aliens, the\n Louvain-la-Neuve municipal government decided to take\n precautionary measures; they built shelters in order to shelter\n everyone in the city in the event of an extraterrestial\n attack.\u003c/p\u003e\n \u003cp\u003eSeveral alien-proof shelters have been erected throughout\n the city, where citizens can weather an alien invasion.\n However, due to municipal regulations and local building codes\n the shelters are limited in size. This makes it necessary for\n the government to assign every citizen a shelter to calmly\n direct themselves towards in the rare event of a fleet of UFOs\n blotting out the sun. Conditional on no shelter being assigned\n more people than it can fit, it is of the utmost importance\n that the time it takes until everyone has arrived at a shelter\n is minimized.\u003c/p\u003e\n \u003cp\u003eWe model Louvain-la-Neuve as a network of \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e locations at which people live,\n connected by \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n bidirectional roads. Located at \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e points throughout the city are the\n shelters, each with a given maximum capacity. What is the\n minimum amount of time it takes for everyone to arrive at a\n shelter, when we assign people to shelters optimally?\u003c/p\u003e\n \u003cp\u003eThe Louvain-la-Neuve municipal government has made sure that\n there is enough shelter capacity for its citizens and all\n shelters can be reached from any location, i.e. it is always\n possible to shelter everyone in some way.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOn the first line are three integers, the number of\n locations \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq\n 10^5$\u003c/span\u003e, roads \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq m\n \\leq 2\\cdot 10^5$\u003c/span\u003e, and shelters \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq s \\leq 10$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThen follows a line with \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e integers \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq p_ i \\leq 10^9$\u003c/span\u003e,\n indicating the the number of people living at location\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq i \\leq n$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThen follow \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e\n lines containing three integers \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq u, v \\leq n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq w \\leq 10^9$\u003c/span\u003e\n indicating that there is a bidirectional road connecting\n \u003cspan class\u003d\"tex2jax_process\"\u003e$u$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$v$\u003c/span\u003e that takes \u003cspan class\u003d\"tex2jax_process\"\u003e$w$\u003c/span\u003e time to traverse. For any two\n locations there is at most one road connecting them\n directly, and no road connects a location to itself.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eFinally follow \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e\n lines with two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\leq s_ i \\leq n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c_ i \\leq 10^9$\u003c/span\u003e,\n indicating that there is a shelter with capacity\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c_ i$\u003c/span\u003e at location\n \u003cspan class\u003d\"tex2jax_process\"\u003e$s_ i$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003ePrint the minimum amount of time it takes to shelter\n everyone.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 1\n3 2\n1 2 4\n1 6\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4 5 2\n2 0 0 2\n1 2 6\n1 3 2\n2 3 3\n3 4 4\n4 2 6\n3 2\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 3\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e7 8 3\n0 1 1 1 1 0 2\n1 2 1\n2 3 1\n3 1 1\n4 6 5\n4 3 1\n6 7 10\n7 5 3\n5 6 3\n6 5\n1 1\n2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 4\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e2 1 1\n0 2\n1 2 1000000000\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}