Orienteering(オリエンテーリング) - joi2011-day4

時間制限: 1秒

メモリ制限: 64MB

あなたの通う JOI 高校では，年に一度，オリエンテーリングが行われ，全校生徒が参加する．オリエンテーリングとは，地図と方位磁針を用い，山野に設置されたチェックポイントを巡る競技である．

JOI 高校のオリエンテーリングは，2 人一組のチームで参加するという特徴がある．各チームの 2 人は，指定されたスタート地点から一緒にスタートするが，その後は別々に行動をし，指定されたゴール地点を目指す．2 人がゴール地点に到達した際，それぞれのチェックポイントをチームのうちの少なくとも 1 人が訪れていないとならない．2 人は途中で同じ地点を訪れても構わない．また，2 人が途中で同じ道を通っても構わない．

JOI 高校のオリエンテーリングが行われる JOI 山には，N 個の地点があり，それらの間を M 本の道が繋いでいる．N 個の地点には 1 から N までの番号が付いている．スタートはふもとにある地点 1 であり，ゴールは頂上の地点 N である．スタートとゴール以外の地点のうち一部または全部がチェックポイントとして指定される．

JOI 高校は，混乱を避けるため，オリエンテーリングの間，それぞれの道を，高度が低い方の地点から高度が高い方の地点への一方通行とする．高度が等しい 2 つの地点は存在しない．スタートである地点 1 は最も高度の低い地点であり，ゴールである地点 N は最も高度の高い地点であるが，地点の番号は必ずしも高度の低い地点から順につけられているわけではないことに注意せよ．JOI 山では，このように道を一方通行にしても，地点 1 から全ての地点に行くことができ，また，全ての地点から地点 N に行くことができる．

課題

条件を満たすような一組のチームの 2 人の移動方法に関して，移動距離の合計の最小値を求めるプログラムを作成せよ．そのような 2 人の移動方法が存在することは保証されている．

制限

`3 \leq N \leq 1\,000`	地点の個数
`2 \leq M \leq 10\,000`	道の本数
`1 \leq K \leq N – 2`	チェックポイントの数
`1 \leq C_j \leq 10\,000`	道 `j` の長さ

入力

標準入力から以下の入力を読み込め．

1 行目には整数 N, M が空白を区切りとして書かれており，地点の数が N 個，道の数が M 本であることを表す．
続く N 行には各地点がチェックポイントであるかどうかの情報が書かれている．1 + i 行目 (1 \leq i \leq N) には，0 か 1 の整数 S_i が書かれており，S_i が 0 の場合，地点 i はチェックポイントではなく，S_i が 1 の場合，地点 i はチェックポイントであることを表す．常に S_1 = S_N = 0 である．
続く M 行には道の情報が書かれている．1 + N + j 行目 (1 \leq j \leq M) には，整数 A_j, B_j, C j が空白を区切りとして書かれており，道 j は地点 A_j から地点 B_j を結び，道 j の長さが C_j であることを表す．地点 A_j は地点 B_j より高度が低い地点であり，道 j は地点 A_j から地点 B_j への一方通行となるものとする．必ず A_j , B_j であり，また，A_j = A_k かつ B_j = B_k なる道 k (k \neq j) は存在しない．

出力

条件を満たすような一組のチームの 2 人の移動方法に関する，移動距離の合計の最小値を出力せよ．

採点基準

以下，チェックポイントの数を K とおく．すなわち，K = S 1 + S 2 + … + S N である．

採点用データのうち，配点の 30% 分については，K \leq 10 を満たす．
採点用データのうち，配点の 30% 分については，N \leq 100 かつ M \leq 500 を満たす．
採点用データのうち，配点の 10% 分については，これら 2 つの条件の両方を満たす.
採点用データのうち，配点の 50% 分については，これら 2 つの条件の少なくとも一方を満たす.

入出力の例

入力例	出力例
`8 12 0 1 0 0 1 1 0 0 1 4 5 1 6 5 4 2 4 4 7 9 4 5 6 2 5 8 2 8 3 6 2 7 6 7 8 7 3 2 3 5 7 5 8 3`	`29`

この入力例は，下図に対応する．チェックポイントとなっている地点は水色で示されている．また，最小の移動距離を達成する 2 人の移動方法は赤色で示されている．