{"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:32.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/15971e0befab6218954927145962cc0d?v\u003d1715690207\" alt\u003d\"/problems/highwayhassle/file/statement/en/img-0001.png\" class\u003d\"illustration\"\u003e\n\n \n \u003c/div\u003e\n\n \u003cp\u003eA transport company has come to you for help. One of the\n biggest expenses that they have is the petrol for the trucks.\n They would like to minimize the money they need to spend on\n petrol.\u003c/p\u003e\n\n \u003cp\u003eBecause of the long trips, a truck driver typically needs to\n stop multiple times at a petrol station to tank up. What\n complicates matters is that the price of petrol is not the same\n at every station. The differences could in fact be so\n significant that it pays to take a detour in order to visit a\n station with a low price. Yet another complication is that the\n price is not the same every day (but it does not change during\n the day).\u003c/p\u003e\n\n \u003cp\u003eThe good news is that they can find out, every morning, what\n the price of petrol is at every station for that day. They also\n have, for every destination, a simple graph representing the\n relevant part of the road network, containing only the major\n intersections and petrol stations as nodes. Furthermore, they\n know for every road exactly how much petrol is needed to go\n from one node to the other, down to the milliliter; it does not\n depend on the direction or the amount of petrol in the tank.\n The truck drivers also have the ability to tank with milliliter\n precision.\u003c/p\u003e\n\n \u003cp\u003eIt is perfectly fine for a truck to run out of petrol at the\n exact moment it arrives at a petrol station or at the\n destination; there is in fact a spare tank to allow for small\n fluctuations in fuel consumption, but that petrol is not\n supposed to be used. You may therefore ignore its\n existence.\u003c/p\u003e\n\n \u003cp\u003eA final thing to take into consideration is that the trucks\n have a fuel tank of limited size. With all that information,\n can you work out what the optimal path to the destination is,\n along with the optimal tanking strategy?\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eOn the first line one positive number: the number of test\n cases, at most 100. After that per test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with three space-separated integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\leq n \\leq 1\\, 000$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq m \\leq 10\\,\n 000$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq s\n \\leq 120$\u003c/span\u003e): the number of nodes, edges and petrol\n stations, respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eone line with a single integer \u003cspan class\u003d\"tex2jax_process\"\u003e$t$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq t \\leq 100\\, 000$\u003c/span\u003e): the\n maximum amount of petrol that the fuel tank can hold in\n milliliters.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines, each\n with three space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq a,b \\leq n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a \\neq b$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq f \\leq 100\\,\n 000$\u003c/span\u003e), indicating that there is a road between nodes\n \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e which takes \u003cspan class\u003d\"tex2jax_process\"\u003e$f$\u003c/span\u003e milliliters of petrol (fuel)\n to traverse.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$s$\u003c/span\u003e lines, each\n with two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq x \\leq n$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq p \\leq 100$\u003c/span\u003e): the node\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x$\u003c/span\u003e where each petrol\n station is located and the price \u003cspan class\u003d\"tex2jax_process\"\u003e$p$\u003c/span\u003e per milliliter of petrol at\n that station, respectively.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eone line with two space-separated integers \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$d$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq c,d \\leq n$\u003c/span\u003e and\n \u003cspan class\u003d\"tex2jax_process\"\u003e$c \\neq d$\u003c/span\u003e): the nodes\n where the company and the destination are located,\n respectively.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eEvery road is bidirectional. There is at most one road\n between any pair of nodes. There is always a petrol station at\n node \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e (it is right next\n to the company). The truck starts with an empty tank. The\n destination is guaranteed to be reachable.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003ePer test case:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eone line with a single integer: the minimum amount of\n money that needs to be spent on petrol.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\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\u003e3\n3 3 2\n2000\n1 3 800\n1 2 500\n2 3 500\n1 70\n2 40\n1 3\n5 5 3\n1000\n1 2 800\n2 5 800\n1 3 400\n3 4 600\n4 5 600\n1 80\n2 90\n3 20\n1 5\n4 3 3\n1000\n1 2 200\n2 3 600\n3 4 300\n1 40\n2 70\n3 90\n2 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e55000\n134000\n61000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}