prithivMLmods/Coder-Stat

1 2 3 4<H1>自転車でダイエット</H1>5 6<p>7  A さんは甘いものが大好きですが、最近は奥さんからダイエットするように言われています。ある日、A さんが自宅から市役所に出かけるとき、奥さんは自転車で行くことを勧めました。そこでA さんはしぶしぶ自転車に乗って出かけましたが、甘い物の好きな A さんは、途中にあるケーキ屋さんに立ち寄りケーキの食べ歩きをしようと思いつきました。8</p>9 10<p>11  自転車をこげば走行距離に応じてカロリーが消費されますが、ケーキを食べればその分カロリーが摂取されます。正味の消費カロリーは、自転車をこいで消費したカロリーからケーキを食べて摂取したカロリーを引いた値になります。したがって、正味の消費カロリーが 0 より小さくなることもあります。12</p>13 14<p>15  ケーキ屋さんでケーキを買ったら、 Aさんはその場でケーキを全部食べてしまいます。 Aさんがすべてのケーキ屋さんに立ち寄るとは限りませんが、ケーキ屋さんが存在する地点を通るときには、必ず立ち寄ってケーキを 1 つ買って食べるものとします。ただし、同じケーキ屋さんの前を何度も通るのはさすがに気がひけるので、各ケーキ屋さんに訪れられるのは 1 回だけとします。また、目的地の市役所をいったん通り過ぎてからケーキ屋さんに立ち寄り、その後で市役所に戻って用を済ませてもよいものとし、ケーキ屋さん以外は何度訪れても良いものとします。16</p>17 18<p>19  A さんの自宅から市役所までの地図情報と、その途中にあるケーキ屋さんで食べられるケーキのカロリーの一覧、単位距離の走行による消費カロリーを入力とし、自宅を出発してから市役所に入るまでの正味の消費カロリーの最小値を出力するプログラムを作成してください。20</p>21 22<p>23  地図には、A さんの自宅と市役所、ケーキ屋さんとランドマーク(目印)になる建物が書かれています。地図を表す入力データは、A さんの自宅、市役所、ケーキ屋さんとランドマークの各地点の間をつなぐ道があるとき、2 つの地点を表す記号とその間の距離からなる行を含みます。たとえば、5 番目のケーキ屋さんと 3 番目のランドマークの間の距離が 10 なら、入力データは以下のような行を含みます。24</p>25 26<pre>27C5 L3 1028</pre>29 30<p>31  このようにケーキ屋さんには C、ランドマークには L を番号の前につけて表します。また、A さんの自宅は H、市役所は D で表します。入力データに 2 つの地点とその間の距離が与えられているなら、2 地点の間をどちら向きにも進めます。たとえば、上の例ではケーキ屋さんからランドマークへも、その逆向きへも進むことができます。また、自宅から市役所までは必ずたどり着けるものとします。それ以外に与えられる入力データは、ケーキ屋さんの数 <var>m</var>、ランドマークの数 <var>n</var>、単位距離あたりの消費カロリー <var>k</var>、 1 番目のケーキ屋さんから <var>m</var> 番目のケーキ屋さんまでのそれぞれで買えるケーキのカロリーを表す <var>m</var> 個のデータ、距離のデータの総数 <var>d</var> です。32</p>33 34 35<H2>Input</H2>36 37<p>38  複数のデータセットの並びが入力として与えられます。入力の終わりは四つの 0 の行で示されます。39  各データセットは以下の形式で与えられます。40</p>41 42<pre>43<var>m</var> <var>n</var> <var>k</var> <var>d</var>44<var>c<sub>1</sub></var> <var>c<sub>2</sub></var> ... <var>c<sub>m</sub></var>45<var>s<sub>1</sub></var> <var>t<sub>1</sub></var> <var>e<sub>1</sub></var>46<var>s<sub>2</sub></var> <var>t<sub>2</sub></var> <var>e<sub>2</sub></var>47:48<var>s<sub>d</sub></var> <var>t<sub>d</sub></var> <var>e<sub>d</sub></var>49</pre>50 51<p>521 行目にケーキ屋さんの数 <var>m</var> (1 &le; <var>m</var> &le; 6)、 ランドマークの数 <var>n</var> (1 &le; <var>n</var> &le; 100) 、単位距離あたりの消費カロリー <var>k</var> (1 &le; <var>k</var> &le; 5)、距離のデータの総数 <var>d</var> (5 &le; <var>d</var> &le; 256) が与えられます。53</p>54 55<p>562 行目に各ケーキ屋で買うケーキのカロリー <var>c<sub>i</sub></var> (1 &le; <var>c<sub>i</sub></var> &le; 100) が与えられます。57</p>58 59<p>60続く <var>d</var> 行に <var>i</var> 番目の 2 つの地点間の距離データ <var>s<sub>i</sub></var>, <var>t<sub>i</sub></var>, <var>e<sub>i</sub></var> (1 &le; <var>e<sub>i</sub></var> &le; 20)  が与えられます。61</p>62 63<p>64データセットの数は 100 を超えません。65</p>66 67 68<H2>Output</H2>69 70<p>71入力データセットごとに、全体の消費カロリーの最小値を１行に出力します。72</p>73 74<H2>Sample Input</H2>75 76<pre>771 1 2 5783579H L1 580C1 D 681C1 H 1282L1 D 1083C1 L1 20842 1 4 685100 7086H L1 587C1 L1 1288C1 D 1189C2 L1 790C2 D 1591L1 D 8920 0 0 093</pre>94 95<H2>Output for the Sample Input</H2>96 97<pre>98199-2100</pre>101 102 103