prithivMLmods/Coder-Stat

1 2 3<H1><font color="#000000">Problem 08:</font> Provident Housewife</H1>4 5<p>6主婦の琴子はこの不況のさなか食費を抑えることに闘志を燃やしていました。毎朝新聞広告を必ずチェック。買う物リストと最も安く売られているお店をしっかりリストアップして、お店をはしごしながら、エプロン・サンダルという戦闘スタイルで自転車をこぎこぎ買い物に行きます。7</p>8 9<p>10そこで夫のあなたは少しでも琴子の役に立とうと、得意のプログラミングで家計簿プログラムを作成することにしました。プログラムは、各スーパーに売っている品物の名前と値段（円）、琴子が必要な品物を入力し、全ての品物を集めるための最小金額を出力します。11</p>12 13<p>14琴子は家を出て必要な品物を集め、家に戻ってこなければなりません。15そこで、琴子を気遣ったあなたは、最小金額が同じになる買い物ルートが複数ある場合も考慮して、より距離が短くなるルートの距離を報告する機能を追加することにしました。従って、プログラムはスーパー・家間を繋ぐ道の情報も入力します。16</p>17 18<p>19スーパーの数を <i>n</i> とし、各スーパーにはそれぞれ 1 から <i>n</i> までの番号が割り当てられます。さらに琴子の家を 0 番とします。道の情報はこれらの番号のペアとその距離（整数）で与えられます。20</p>21 22 23<H2>Input</H2>24<p>25入力として複数のデータセットが与えられます。各データセットの形式は以下の通りです：<br>26<br>27<i>n</i>　（スーパーの数：整数）<br>28<i>k</i><sub>1</sub> <i>name</i><sub>1</sub> <i>value</i><sub>1</sub> <i>name</i><sub>2</sub> <i>value</i><sub>2</sub> . . . <i>name</i><sub><i>k</i><sub>1</sub></sub> <i>value</i><sub><i>k</i><sub>1</sub></sub>（1 番目のスーパーにある品物の種類の数、1つ目の品物名と値段、2つ目の品物名と値段,,,：整数と文字列の空白区切り）<br>29<i>k</i><sub>2</sub> <i>name</i><sub>1</sub> <i>value</i><sub>1</sub> <i>name</i><sub>2</sub> <i>value</i><sub>2</sub> . . . <i>name</i><sub><i>k</i><sub>2</sub></sub> <i>value</i><sub><i>k</i><sub>2</sub></sub>（2 番目のスーパーにある品物の種類の数、1つ目の品物名と値段、2つ目の品物名と値段,,,：整数と文字列の空白区切り）<br>30.<br>31.<br>32<i>k</i><sub><i>n</i></sub> <i>name</i><sub>1</sub> <i>value</i><sub>1</sub> <i>name</i><sub>2</sub> <i>value</i><sub>2</sub> . . . <i>name</i><sub><i>k</i><sub><i>n</i></sub></sub> <i>value</i><sub><i>k</i><sub><i>n</i></sub></sub>（<i>n</i> 番目のスーパーにある品物の種類の数、1つ目の品物名と値段、2つ目の品物名と値段,,,：整数と文字列の空白区切り）<br>33<i>q</i>　（必要な品物の数：整数）<br>34<i>name</i><sub>1</sub>　（1 つ目の必要な品物の名前：文字列）<br>35<i>name</i><sub>2</sub>　（2 つ目の必要な品物の名前：文字列）<br>36.<br>37.<br>38<i>name</i><sub><i>q</i></sub>　（<i>q</i> つ目の必要な品物の名前：文字列）<br>39<i>m</i>　（道の数：整数）<br>40<i>s</i><sub>1</sub> <i>t</i><sub>1</sub> <i>d</i><sub>1</sub>　（1 本目の道の情報：空白区切りの整数）<br>41<i>s</i><sub>2</sub> <i>t</i><sub>2</sub> <i>d</i><sub>2</sub>　（2 本目の道の情報：空白区切りの整数）<br>42.<br>43.<br>44<i>s</i><sub><i>m</i></sub> <i>t</i><sub><i>m</i></sub> <i>d</i><sub><i>m</i></sub>　（<i>m</i> 本目の道の情報：空白区切りの整数）<br>45</p>46 47<p>48<i>s<sub>i</sub></i> <i>t<sub>i</sub></i> <i>d<sub>i</sub></i> は <i>s<sub>i</sub></i>番目のスーパー（または家）と <i>t<sub>i</sub></i>番目のスーパー（または家）が双方向に行き来することができ、その距離が <i>d<sub>i</sub></i>であることを示します。49</p>50 51<p>52家から（スーパーを経由して）全てのスーパーへ行くことができるような道が与えられます。53</p>54 55<p>56<i>n</i> は 10 以下であり、<i>q</i> は 15 以下とします。57<i>k<sub>i</sub></i> は 100 以下であり、58品物名の文字列は 20文字を越ず、品物の値段は 10000 を越えません。59また、道の長さは 1000 を越えません。60</p>61 62<p>63<i>n</i> が 0 のとき、入力の終わりとします。64</p>65 66<H2>Output</H2>67 68<p>69各データセットについて、最小の金額と距離を１つの空白で区切って１行に出力して下さい。ただし、必要な品物を全て集められない場合は "<span>impossible</span>" と出力して下さい。70</p>71 72<H2>Sample Input</H2>73<pre>743753 apple 100 banana 200 egg 300763 apple 150 banana 100 cola 200773 apple 100 banana 150 cola 20078379apple80banana81cola825830 2 4840 1 3850 3 3861 2 3872 3 5883893 apple 100 banana 200 egg 300903 apple 150 banana 100 cola 200913 apple 100 banana 150 cola 20092493apple94banana95cola96jump975980 2 4990 1 31000 3 31011 2 31022 3 51030104</pre>105 106 107<H2>Output for the Sample Input</H2>108<pre>109400 10110impossible111</pre>112