象使い (Route)
時間制限 : 1sec / スタック制限 : 64MB / メモリ制限 : 64MB
あなたの友人の象使いは王宮まで象をつれて行くことを命ぜられた．道路図が与えられるが,王宮までの道路はそれぞれ有料で，さらにその費用は自前で用意しなければならない．彼のために最も安い道程を探し出して欲しい．
ただし，以下のことに注意すること．
- 道路は2つの料金所の間を結ぶ線分である．2つの料金所p, q の組に対して，p とq を結ぶ道路は高々1 本しか存在しない．
- 道路は必ず端点から端点までたどらなければならず，途中でほかの道路に乗り換えることはできない．
- 象は鋭角には曲れないため，料金所では，それまでたどった道路とのなす角が鋭角になる道路には乗り換えられない. 例えば，下の図では，p → q → r はたどれず，u → v → wやx → y → z はたどれる．
入力
入力ファイルroute.in の1 行目には，料金所の数n (2 ≦ n ≦ 100) と道路の数m が空白で区切られて書かれている．i + 1 行目(1 ≦ i ≦ n) には，2つの整数xi, yi (-10000 ≦ xi ≦ 10000, -10000 ≦ yi ≦ 10000) が空白で区切られて書かれている．これは，i 番目の料金所の座標が(xi, yi) であることを表わしている．j+n+1 行目(1 ≦ j ≦ m) には，3つの整数aj , bj , cj (1 ≦ aj < bj ≦ n, 0 ≦ cj ≦ 10000) が空白で区切られて書かれている. これは，aj 番目の料金所とbj 番目の料金所で結ばれる道路の通行料金がcj であることを表わしている．
現在の象の居場所は1 番目の料金所である．王宮は2 番目の料金所のすぐ近くにある．
出力
1 番目の料金所から2 番目の料金所へ到達できる，最も安い料金を出力せよ．もし到達不可能な場合は，-1 を出力せよ．
入出力例
| 入力例1 |
出力例1 |
5 6
0 0
10 10
0 10
10 0
2 -6
1 2 30
1 3 4
1 4 5
1 5 1
2 4 3
2 5 1 |
8 |
1 番目の料金所から2 番目の料金所への道程は，1 → 2 と1 → 4 → 2 の2 つがあり，そのうち料金が安い1 → 4 → 2 の料金8 を出力する．1 → 5 → 2 は，料金2 だが，道路1 → 5 と道路5 → 2 が5 番目の料金所で鋭角をなすので，象は1 → 5 → 2 とたどることはできない．
コメント
最終更新：2013年02月23日 22:44
