{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e div.illustration { float: right; padding-left: 20px; } div.illustration .illustration { width: 100%; border-radius: 4px; }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}\u003c/style\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/29e3e7a2a23f0b1849b978e25da93b3e?v\u003d1685047618\" alt\u003d\"/problems/charlesincharge/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n\u003c/div\u003e\n\u003cp\u003eEvery day, Charles drives from his home to work and back. He uses the highways of the country that run from one city to another. Charles has decided that he wants to help the environment by buying an electrical car. Electrical cars, however, are not very common in his country yet. They can only be charged inside a city; there are no charging stations along the highways in between the cities. Moreover, all electrical cars are identical except for one thing: the size of the battery. As batteries are very expensive, Charles would like to buy a car with battery that is as small as possible.\u003c/p\u003e\n\u003cp\u003eHowever, this greatly increases the time it takes for him to get home, much to the distaste of his wife, Charlotte. This has spawned an argument, and after much discussion they have decided to compromise: Charlotte is fine with Charles taking a longer route, as long as it its length is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$X \\% $\u003c/span\u003e longer than the length of shortest route that Charles could have taken to get home from work by using a regular car. Charles has agreed with this, and he now wants to find a route that minimizes the size of the car battery that he needs, i.e.\u0026nbsp;the route that minimizes the maximum distance that Charles has to drive on a highway without passing through a city.\u003c/p\u003e\n\u003cp\u003eThe amount of time Charles spends to charge his car can be neglected.\u003c/p\u003e\n\u003cdiv id\u003d\"a0000000004\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/2c9ad8e1ab529732c0f44f92b4e98c2a?v\u003d1685047618\" alt\u003d\"\\includegraphics[width\u003d0.5\\textwidth ]{testcase.pdf}\" style\u003d\"width:50.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: The graph of the second and third test case. The shortest path has length \u003cspan class\u003d\"tex2jax_process\"\u003e$16$\u003c/span\u003e. In the second testcase, Charles’s travel distance may not exceed \u003cspan class\u003d\"tex2jax_process\"\u003e$16 \\cdot 1.15 \u003d 18.4$\u003c/span\u003e distance units. As a result, he cannot use a battery with which he can travel \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e distance units, as the red path \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$6$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e has length \u003cspan class\u003d\"tex2jax_process\"\u003e$20$\u003c/span\u003e. Therefore, he uses the blue path \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$7$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$8$\u003c/span\u003e–\u003cspan class\u003d\"tex2jax_process\"\u003e$9$\u003c/span\u003e, which has length \u003cspan class\u003d\"tex2jax_process\"\u003e$18$\u003c/span\u003e, and the longest edge has length \u003cspan class\u003d\"tex2jax_process\"\u003e$5$\u003c/span\u003e. In the third test case, he is allowed to travel \u003cspan class\u003d\"tex2jax_process\"\u003e$16 \\cdot 1.30 \u003d 20.8$\u003c/span\u003e distance units, so he can follow the red path, where the longest edge has length \u003cspan class\u003d\"tex2jax_process\"\u003e$4$\u003c/span\u003e.\n \u003c/div\u003e\n \u003c/center\u003e\n\u003c/div\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003eThe input starts with integers \u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq N \\leq 10\\, 000$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq M \\leq 100\\, 000$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\leq X \\leq 10\\, 000$\u003c/span\u003e: the number of cities, the number of highways connecting the cities and the aforementioned percentage \u003cspan class\u003d\"tex2jax_process\"\u003e$X$\u003c/span\u003e. City \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e is the place where Charles lives and city \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e is where he works.\u003c/p\u003e\n\u003cp\u003eThen follow \u003cspan class\u003d\"tex2jax_process\"\u003e$M$\u003c/span\u003e lines with on each line three integers: \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq C_1 \\leq N$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq C_2 \\leq N$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq T \\leq 10^9$\u003c/span\u003e. This means that there is a highway of length \u003cspan class\u003d\"tex2jax_process\"\u003e$T$\u003c/span\u003e connecting cities \u003cspan class\u003d\"tex2jax_process\"\u003e$C_1$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$C_2$\u003c/span\u003e (Charles can traverse the highway in both directions) \u003cem\u003ewithout\u003c/em\u003e passing through any other cities. You may assume that there exists a path from city \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to city \u003cspan class\u003d\"tex2jax_process\"\u003e$N$\u003c/span\u003e.\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003eThe output is a single integer: the smallest maximum distance that Charles has to travel on a highway without passing through a city, such that the route he takes is at most \u003cspan class\u003d\"tex2jax_process\"\u003e$X\\% $\u003c/span\u003e longer than the shortest route.\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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 100\n1 2 5\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"}},{"title":"Sample 2","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e9 8 15\n1 9 16\n1 4 4\n4 5 4\n5 6 4\n6 8 4\n4 7 5\n7 8 5\n8 9 4\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"}},{"title":"Sample 3","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\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\u003e9 8 30\n1 9 16\n1 4 4\n4 5 4\n5 6 4\n6 8 4\n4 7 5\n7 8 5\n8 9 4\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"}}]}