prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});4</script>5<script type='text/javascript' src='http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML'></script>6</script>7 8 9<h2>Problem I10Routing a Marathon Race</h2>11 12 13<p>14As a member of the ICPC (Ibaraki Committee of Physical Competitions), you are responsible for planning the route of a marathon event held in the City of Tsukuba. A great number of runners, from beginners to experts, are expected to take part.15</p>16 17<p>18You have at hand a city map that lists all the street segments suited for the event and all the junctions on them. The race is to start at the junction in front of Tsukuba High, and the goal is at the junction in front of City Hall, both of which are marked on the map.19</p>20 21<p>22To avoid congestion and confusion of runners of divergent skills, the route should not visit the same junction twice. Consequently, although the street segments can be used in either direction, they can be included at most once in the route. As the main objective of the event is in recreation and health promotion of citizens, time records are not important and the route distance can be arbitrarily decided.23</p>24 25<p>26A number of personnel have to be stationed at every junction on the route. Junctions <i>adjacent</i> to them, i.e., junctions connected directly by a street segment to the junctions on the route, also need personnel staffing to keep casual traffic from interfering the race. The same number of personnel is required when a junction is on the route and when it is adjacent to one, but different junctions require different numbers of personnel depending on their sizes and shapes, which are also indicated on the map.27</p>28 29<p>30The municipal authorities are eager in reducing the costs including the personnel expense for31events of this kind. Your task is to write a program that plans a route with the minimum32possible number of personnel required and outputs that number.33</p>34 35 36<h3>Input</h3>37 38<p>39The input consists of a single test case representing a summary city map, formatted as follows.<br>40<br>41 42$n$ $m$<br>43$c_1$<br>44...<br>45$c_n$<br>46$i_1$ $j_1$<br>47...<br>48$i_m$ $j_m$<br>49<br>50 51The first line of a test case has two positive integers, $n$ and $m$. Here, $n$ indicates the number of junctions in the map $(2 \leq n \leq 40)$, and $m$ is the number of street segments connecting adjacent junctions. Junctions are identified by integers 1 through $n$.52</p>53 54<p>55Then comes $n$ lines indicating numbers of personnel required. The $k$-th line of which, an integer $c_k$ $(1 \leq c_k \leq 100)$, is the number of personnel required for the junction $k$.56</p>57 58<p>59The remaining $m$ lines list street segments between junctions. Each of these lines has two integers $i_k$ and $j_k$, representing a segment connecting junctions $i_k$ and $j_k$ $(i_k \ne j_k)$. There is at most one street segment connecting the same pair of junctions.60</p>61 62<p>63The race starts at junction 1 and the goal is at junction $n$. It is guaranteed that there is at least one route connecting the start and the goal junctions.64</p>65 66<h3>Output</h3>67 68<p>69Output an integer indicating the minimum possible number of personnel required.70</p>71 72<center>73<img src="https://judgeapi.u-aizu.ac.jp/resources/images/IMAGE2_ICPCAsia2015_RoutingAMarathonRace"><br>74<p>75Figure I.1. The Lowest-Cost Route for Sample Input 176</p>77</center>78 79<p>80Figure I.1 shows the lowest-cost route for Sample Input 1. The arrows indicate the route and the circles painted gray are junctions requiring personnel assignment. The minimum number of required personnel is 17 in this case.81</p>82 83<h3>Sample Input 1</h3>84 85<pre>6 6863871889894903916921 2931 4942 6955 4966 5973 2</pre>98 99<h3>Sample Output 1</h3>100 101<pre>17</pre>102