Traveling by Stagecoach

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

Problem D: Traveling by Stagecoach

昔,昔のことである. 一人の旅人がいた. 彼は,馬車(駅馬車)を使っての旅行を計画している. 出発地と目的地は決まっているのだが,ルートが決まらなくて困っている. 彼のためにルートを決定するプログラムを書くことがあなたの仕事である.

この国には複数の都市があり,それらの間を結ぶ道路網が整備されている. 道路で直結されている二つの都市の間は,馬車で移動することができる. 馬車に乗るには,馬車券が必要である. それぞれの馬車券には,馬の頭数が指定されている. 当然ながら,頭数の多い馬車ほど速い.

旅人は,出発時に何枚かの馬車券を持っている. 道路網と手持ちの馬車券に関する情報から, どのようなルートを選べば最も早く目的地に着けるかを求めたい. この際,馬車券をどう使えばよいかも考える必要がある.

次のような条件を仮定する.

  • 1台の馬車で移動できるのは,1区間(道路で直結された都市間)だけである. すなわち,都市に到着するたびに馬車を乗り換えなければならない.
  • 1区間に使える馬車券は1枚だけである.
  • 1枚の馬車券は一度しか使えない.
  • 都市間の所要時間は,距離を頭数で割った値である.
  • 乗り換えに要する時間は無視する.

Input

入力は複数のデータセットから構成される. 各データセットの形式は次に示すとおりである. 最後のデータセットの直後に,空白で区切られた五つの0からなる行がある.

n m p a b
t1 t2 ... tn
x1 y1 z1
x2 y2 z2
...
xp yp zp

データセットの中の入力項目は,すべて非負の整数である. 1行の中に二つ以上の入力項目がある場合の区切りは空白1個である.

nは,馬車券の枚数である. 1以上8以下と仮定してよい. mは,都市の数である. 2以上30以下と仮定してよい. pは,都市間道路の本数である. 道路の本数が0のこともある.

aは,出発地の都市番号である. bは,目的地の都市番号である. abと等しくない. この二つを含めて,データセット中に現れる都市番号は1以上m以下と仮定してよい.

データセットの2行目は,出発時に持っている馬車券それぞれに関する情報を表す. tiは,i番目の馬車券(1<=i<=n) に指定された頭数である. 頭数は1以上10以下であると仮定してよい.

これに続くp行が都市間道路の記述である. xiyiが両端の都市番号, ziがその道路に沿った距離である(1<=i<=p). 距離は1以上100以下と仮定してよい.

ある二つの都市を結ぶ道路が2本以上存在することはない. 1本の道路の両端が同じ都市であることはない. それぞれの道路は,どちら向きの移動にも使うことができる.

Output

入力の各データセットに対して,以下に規定する結果を一つの行として出力しなさい. 出力行の中に,結果を表す文字以外のもの(たとえば空白)が含まれていてはならない.

目的地に到達できる場合は, 最も所要時間の短いルートを選んだ時の所要時間を出力すること. 答には,0.001を越える誤差があってはいけない. この条件を守る限り,小数点以下に何個の数字を出力してもよい.

目的地に到達できない場合は,Impossibleと出力すること. これに該当するのは, 到達できるルートが存在しない場合と馬車券の枚数が足りない場合である. Impossibleは,最初の文字が大文字,ほかが小文字であることに注意.

Sample Input

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

Output for the Sample Input

30.000
3.667
Impossible
Impossible
2.856

Source: ACM International Collegiate Programming Contest , Japan Domestic Contest, Tokyo, Japan, 2005-07-01
http://www2.teu.ac.jp/icpc/