{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eThe government of \u003cstrong\u003eSpoj_land\u003c/strong\u003e has selected a number of locations in the city for road construction and numbered those locations as 0, 1, 2, 3, ... 500.\u003c/p\u003e\r\n\u003cp\u003eNow, they want to construct roads between various pairs of location (say \u003cstrong\u003eA\u003c/strong\u003e and \u003cstrong\u003eB\u003c/strong\u003e) and have fixed the cost for travelling between those pair of locations from either end as \u003cstrong\u003eW unit\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003eNow, Rohit being a curious boy wants to find the minimum cost for travelling from location \u003cstrong\u003eU\u003c/strong\u003e (source) to \u003cstrong\u003eQ\u003c/strong\u003e number of other locations (destination).\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cp\u003eFirst line contains \u003cstrong\u003eN\u003c/strong\u003e ,the number of roads that government constructed.\u003c/p\u003e\r\n\u003cp\u003eNext N line contains three integers \u003cstrong\u003eA\u003c/strong\u003e ,\u003cstrong\u003eB\u003c/strong\u003e, and \u003cstrong\u003eW\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003eA and B represent the locations between which the road was constructed and W is the fixed cost for travelling from A to B or from B to A.\u003c/p\u003e\r\n\u003cp\u003eNext line contains an integer \u003cstrong\u003eU\u003c/strong\u003e from where Rohit wants to travel to other locations.\u003c/p\u003e\r\n\u003cp\u003eNext line contain \u003cstrong\u003eQ\u003c/strong\u003e, the number of queries (finding cost) that he wants to perform.\u003c/p\u003e\r\n\u003cp\u003eNext \u003cstrong\u003eQ\u003c/strong\u003e lines contain an integer \u003cstrong\u003eV\u003c/strong\u003e (destination) for which minimum cost is to be found \u003cstrong\u003efrom U\u003c/strong\u003e.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cp\u003ePrint the required answer in each line.\u003c/p\u003e\r\n\u003cp\u003eIf he can\u0027t travel from location U to V by any means then, print \u0027\u003cstrong\u003eNO PATH\u003c/strong\u003e\u0027 without quotes.\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\u003cdiv\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\r\n0 1 4\r\n0 3 8\r\n1 4 1\r\n1 2 2\r\n4 2 3\r\n2 5 3\r\n3 4 2\r\n0\r\n4\r\n1\r\n4\r\n5\r\n7\r\n\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n5\r\n9\r\nNO PATH\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/div\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\u003cp\u003e1 \u0026lt;\u003d N \u0026lt;\u003d 500\u003c/p\u003e\r\n\u003cp\u003e0 \u0026lt;\u003d A, B \u0026lt;\u003d 500\u003c/p\u003e\r\n\u003cp\u003e1 \u0026lt;\u003d W \u0026lt;\u003d 100\u003c/p\u003e\r\n\u003cp\u003e0 \u0026lt;\u003d U, V \u0026lt;\u003d 500\u003c/p\u003e\r\n\u003cp\u003e1 \u0026lt;\u003d Q \u0026lt;\u003d 500\u003c/p\u003e\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\u003cp\u003eQuery #1: 0 → 1: cost \u003d 4\u003c/p\u003e\r\n\u003cp\u003eQuery #2: 0 → 4: 0 → 1 → 4, cost \u003d 4 + 1 \u003d 5\u003c/p\u003e\r\n\u003cp\u003eQuery #3: 0 → 5: 0 → 1 → 2 → 5, cost \u003d 4 + 2 + 3 \u003d 9\u003c/p\u003e\r\n\u003cp\u003eQuery #4: 0 → 7: no path exist between 0 and 7\u003c/p\u003e\r\n\n\u003c/div\u003e"}}]}