Winter Bells

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

Problem H: Winter Bells

世界で一番とびっきりの夜がやってきた。12月24日午後8時。そう、クリスマスイブの夜である。寝静まった街に、鈴の音を鳴らしながらサンタクロースはやってくる。トナカイのソリに引かれて、北風を追い越し、子供たちの眠る窓辺に吊るされた靴下にプレゼントを撃ち込むのだ。

サンタクロースの乗るソリは、街の外れにある大きなクリスマスツリーから出発する。このクリスマスツリーが生み出す奇跡の力は街の上空に網目のように広がり、ソリが通れるような道を作るのだ。奇跡の力が濃い所ほど通りやすいので、これらの道は重み付き無向グラフとして表すことができる。

サンタクロースにとってプレゼントの配達は、極めて厳しい時間との戦いである。夜明けが近づいてくると奇跡の力は急激に弱まり、サンタクロースは配達を続けられなくなってしまう。そんなことはサンタクロースのプライドが許さないので、何としてもそれまでに配達を住ませなければならないのだ。

トナカイの引くソリは、クリスマスツリー (0番目の頂点に対応する) を出発し、街の反対側 (n-1番目の頂点にに対応する) まで最短経路を通って滑空する。サンタクロースはトナカイが全力で引くソリの上から、奇跡の力をプレゼントに変えて撃ち込むのだ。もし2つ以上の最短経路があった場合、トナカイは全ての最短経路の中から等確率で一つを選び、それに沿ってソリを走らせる。

さて、この街には p 人の子供たちがいて、サンタクロースを一目見たいと思いながら、自分の部屋の窓から夜空を見上げている。i 番目の子供の家の上空には、グラフの c[i] 番目の頂点に対応するような奇跡の力の交差点があり、その子供はその頂点をサンタクロースが通過した場合 (また、その場合に限って) サンタクロースを見ることができる。

それぞれの子供がサンタクロースを見られる確率はいくらだろうか?

Input

各データセットの最初の行には3つの整数 n, m, p が与えられる。これらはそれぞれ、グラフの頂点の数、辺の数、そして子供の数を表す。各頂点には 0 から n-1 の番号が付けられている。

続く m 行には辺の情報が与えられる。各行には3つの整数が与えられ、最初の2つの数字はその辺の両端の頂点を、3つ目の数字はその辺の重みを表す。

その次の p 行で c[i] がそれぞれ与えられる。

n, m, p がすべて 0 のとき入力の終わりを示す。

Output

確率を表す p 個の実数値を、入力と同じ順番で出力せよ。その後に1行の空行を出力せよ。 小数点以下何桁でも出力してよく、出力される数は1.0e-6以下の誤差を含んでいても構わない。

Constraints

  • 3 ≤ n ≤ 100
  • グラフに平行辺はなく、両端の頂点が同じであるような辺はない。
  • 少なくとも1つの最短経路が存在する。
  • 0 < 辺の重み < 10000

Sample Input

3 2 1
0 1 2
1 2 3
1
4 5 2
0 1 1
0 2 1
1 2 1
1 3 1
2 3 1
1
2
0 0 0

Output for the Sample Input

1.00000000

0.50000000
0.50000000


Source: University of Aizu Programming Contest , Aizu-Wakamatsu, Japan, 2010-05-29
Problem Setter:  Takashi Tayama