시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 1024 MB | 44 | 24 | 18 | 54.545% |
あなたの友人の象使いは王宮まで象をつれて行くことを命ぜられた.道路図が与えられるが, 王宮までの道路はそれぞれ有料で,さらにその費用は自前で用意しなければならない.
彼のために最も安い道程を探し出して欲しい.
ただし,以下のことに注意すること.
入力の 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 を出力せよ.
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 とたどることはできない.