← 返回题目列表

AtCoder · joisc2007_route

route. Mahout(路线)

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存和染色。

象使い (Route) - 原题 PDF 第 1 页
原题PDF第2页
象使い (Route) - 原题 PDF 第 2 页
原题PDF第3页
可复制的 PDF 提取文本
Route: 象使い


input ファイル“route.in”
output 標準出力
ソースファイルroute.c/route.cpp/Route.java
時間制限1 秒/ データ


 あなたの友人の象使いは王宮まで象をつれて行くことを命ぜられた.道路図が与えられるが,

王宮までの道路はそれぞれ有料で,さらにその費用は自前で用意しなければならない.

 彼のために最も安い道程を探し出して欲しい.

 ただし,以下のことに注意すること.


   • 道路は2つの料金所の間を結ぶ線分である.2つの料金所p, q の組に対して,p とq を

   結ぶ道路は高々1 本しか存在しない.

   • 道路は必ず端点から端点までたどらなければならず,途中でほかの道路に乗り換えること

   はできない.

   • 象は鋭角には曲れないため,料金所では,それまでたどった道路とのなす角が鋭角になる

   道路には乗り換えられない. 例えば,下の図では,p →q →r はたどれず,u →v →w

   やx →y →z はたどれる.



                          q
                                                                          y





                                                                                              z                                                                x                                      u                                                                     w

                p





                                    r                                                       v





                          象使い–1/2

Input.

 入力ファイル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 番目の料金所のすぐ近くにある.

Output. 1 番目の料金所から2 番目の料金所へ到達できる,最も安い料金を出力せよ.もし到

達不可能な場合は,−1 を出力せよ.


例
 route.in 標準出力                                                3
                                                                                                            2
 5 6       8
 0 0
 10 10
 0 10
 10 0
 2 -6
 1 2 30
                                                                         1                                  4
 1 3 4
 1 4 5
 1 5 1
 2 4 3                                                                            5
                                          
 2 5 1

                            入力例の図示        




  1 番目の料金所から2 番目の料金所への道程は,1 →2 と1 →4 →2 の2つがあり,そのう

ち料金が安い1 →4 →2 の料金8 を出力する.1 →5 →2 は,料金2 だが,道路1 ↔5 と道

路5 ↔2 が5 番目の料金所で鋭角をなすので,象は1 →5 →2 とたどることはできない.





                          象使い–2/2