prithivMLmods/Coder-Stat

1 2<script type="text/x-mathjax-config">3  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});4</script>5<script type="text/javascript" async src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS_HTML"></script>6 7 8<h2>Problem F9  Pizza Delivery10  </h2>11 12<p>13  Alyssa is a college student, living in New Tsukuba City. All the streets in the city are one-way. A new social experiment starting tomorrow is on alternative traffic regulation reversing the one-way directions of street sections. Reversals will be on one single street section between two adjacent intersections for each day; the directions of all the other sections will not change, and the reversal will be canceled on the next day.14</p>15 16<p>17Alyssa orders a piece of pizza everyday from the same pizzeria. The pizza is delivered along the shortest route from the intersection with the pizzeria to the intersection with Alyssa's house.18</p>19 20<p>21  Altering the traffic regulation may change the shortest route. Please tell Alyssa how the social experiment will affect the pizza delivery route.22</p>23 24<h3>Input</h3>25<p>26  The input consists of a single test case in the following format.27</p>28 29<pre>30$n$ $m$31$a_1$ $b_1$ $c_1$32...33$a_m$ $b_m$ $c_m$34</pre>35 36<p>37  The first line contains two integers, $n$, the number of intersections, and $m$, the number of street sections in New Tsukuba City ($2 \leq n \leq 100 000, 1 \leq m \leq 100 000$). The intersections are numbered $1$ through $n$ and the street sections are numbered $1$ through $m$.38</p>39 40<p>41  The following $m$ lines contain the information about the street sections, each with three integers $a_i$, $b_i$, and $c_i$ ($1 \leq a_i  n, 1 \leq b_i \leq n, a_i \ne b_i, 1 \leq c_i \leq 100 000$). They mean that the street section numbered $i$ connects two intersections with the one-way direction from $a_i$ to $b_i$, which will be reversed on the $i$-th day. The street section has the length of $c_i$. Note that there may be more than one street section connecting the same pair of intersections.42</p>43 44<p>45  The pizzeria is on the intersection 1 and Alyssa's house is on the intersection 2. It is guaranteed that at least one route exists from the pizzeria to Alyssa's before the social experiment starts.46</p>47 48<h3>Output</h3>49<p>50  The output should contain $m$ lines. The $i$-th line should be51</p>52<ul>53<li> <span>HAPPY</span> if the shortest route on the $i$-th day will become shorter,</li>54<li> <span>SOSO</span> if the length of the shortest route on the $i$-th day will not change, and</li>55<li> <span>SAD</span> if the shortest route on the $i$-th day will be longer or if there will be no route from the pizzeria to Alyssa's house.</li>56</ul>57 58<p>59  Alyssa doesn't mind whether the delivery bike can go back to the pizzeria or not.60</p>61 62 63<h3>Sample Input 1</h3>64<pre>654 5661 3 5673 4 6684 2 7692 1 18702 3 1271</pre>72 73<h3>Sample Output 1</h3>74<pre>75SAD76SAD77SAD78SOSO79HAPPY80</pre>81 82<h3>Sample Input 2</h3>83<pre>847 5851 3 2861 6 3874 2 4886 2 5897 5 690</pre>91 92<h3>Sample Output 2</h3>93<pre>94SOSO95SAD96SOSO97SAD98SOSO99</pre>100 101<h3>Sample Input 3</h3>102<pre>10310 141041 7 91051 8 31062 8 41072 6 111083 7 81093 4 41103 2 11113 2 71124 8 41135 6 111145 8 121156 10 61167 10 81178 3 6118</pre>119 120<h3>Sample Output 3</h3>121<pre>122SOSO123SAD124HAPPY125SOSO126SOSO127SOSO128SAD129SOSO130SOSO131SOSO132SOSO133SOSO134SOSO135SAD136</pre>