{"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 \u003cp\u003eYou are in charge of designing an advanced centralized\n traffic management system for smart cars. The goal is to use\n global information to instruct morning commuters, who must\n drive downtown from the suburbs, how best to get to the city\n center while avoiding traffic jams.\u003c/p\u003e\n\n \u003cp\u003eUnfortunately, since commuters know the city and are\n selfish, you cannot simply tell them to travel routes that take\n longer than normal (otherwise they will just ignore your\n directions). You can only convince them to change to different\n routes that are equally fast.\u003c/p\u003e\n\n \u003cp\u003eThe city’s network of roads consists of intersections that\n are connected by bidirectional roads of various travel times.\n Each commuter starts at some intersection, which may vary from\n commuter to commuter. All commuters end their journeys at the\n same place, which is downtown at intersection 1. If two\n commuters attempt to start travelling along the same road in\n the same direction at the same time, there will be congestion;\n you must avoid this. However, it is fine if two commuters pass\n through the same intersection simultaneously or if they take\n the same road starting at different times.\u003c/p\u003e\n\n \u003cp\u003eDetermine the maximum number of commuters who can drive\n downtown without congestion, subject to all commuters starting\n their journeys at exactly the same time and without any of them\n taking a suboptimal route.\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:congest\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/1cb9741803f4bd22080b3b6271e9f2ab?v\u003d1715752554\" alt\u003d\"\\includegraphics[width\u003d0.4\\textwidth ]{sample}\" style\u003d\"width:40.00%\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of Sample Input 2.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003eIn Figure\u0026nbsp;1, cars are shown in their original\n locations. One car is already downtown. Of the cars at\n intersection 4, one can go along the dotted route through\n intersection 3, and another along the dashed route through\n intersection 2. But the remaining two cars cannot reach\n downtown while avoiding congestion. So a maximum of 3 cars can\n reach downtown with no congestion.\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. The first line\n contains three integers \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$c$\u003c/span\u003e, where \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1\n \\le n \\le 25\\, 000$\u003c/span\u003e) is the number of intersections,\n \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le m \\le 50\\, 000$\u003c/span\u003e) is the number\n of roads, and \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e\n (\u003cspan class\u003d\"tex2jax_process\"\u003e$0 \\le c \\le 1\\, 000$\u003c/span\u003e) is\n the number of commuters. Each of the next \u003cspan class\u003d\"tex2jax_process\"\u003e$m$\u003c/span\u003e lines contains three integers\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e, \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e, and \u003cspan class\u003d\"tex2jax_process\"\u003e$t_ i$\u003c/span\u003e describing one road, where\n \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i$\u003c/span\u003e and \u003cspan class\u003d\"tex2jax_process\"\u003e$y_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le x_ i, y_ i \\le n$\u003c/span\u003e) are the\n distinct intersections the road connects, and \u003cspan class\u003d\"tex2jax_process\"\u003e$t_ i$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le t_ i \\le 10\\, 000$\u003c/span\u003e) is the time\n it takes to travel along that road in either direction. You may\n assume that downtown is reachable from every intersection. The\n last line contains \u003cspan class\u003d\"tex2jax_process\"\u003e$c$\u003c/span\u003e\n integers listing the starting intersections of the\n commuters.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the maximum number of commuters who can reach\n downtown without congestion.\u003c/p\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 3 2\n1 2 42\n2 3 1\n2 3 1\n2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\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 4 5\n1 2 5\n1 3 4\n4 2 5\n4 3 6\n4 4 4 4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}