← 返回题目列表

AtCoder · joisc2011_orienteering

orienteering. 定向运动

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

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

オリエンテーリング (Orienteering) - 原题 PDF 第 1 页
原题PDF第10页
オリエンテーリング (Orienteering) - 原题 PDF 第 2 页
原题PDF第11页
オリエンテーリング (Orienteering) - 原题 PDF 第 3 页
原题PDF第12页
オリエンテーリング (Orienteering) - 原题 PDF 第 4 页
原始PDF第13号
可复制的 PDF 提取文本
Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                      Contest Day 4 – Orienteering

               オリエンテーリング(Orienteering)


 あなたの通う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 ≦N ≦1 000  地点の個数
   2 ≦M ≦10 000 道の本数
   1 ≦K ≦N −2  チェックポイントの数
   1 ≦C j ≦10 000 道j の長さ





                   オリエンテーリング– 1 / 4

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                      Contest Day 4 – Orienteering


入力

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

   • 1 行目には整数N, M が空白を区切りとして書かれており,地点の数がN 個,道の数がM 本である
   ことを表す.

   • 続くN 行には各地点がチェックポイントであるかどうかの情報が書かれている.1+i 行目(1 ≦i ≦N)
   には,0 か1 の整数S i が書かれており,S i が0 の場合,地点i はチェックポイントではなく,S i が
     1 の場合,地点i はチェックポイントであることを表す.常にS 1 = S N = 0 である.

   • 続くM 行には道の情報が書かれている.1 + N + j 行目(1 ≦j ≦M) には,整数Aj, Bj,C j が空白を区
   切りとして書かれており,道j は地点Aj から地点Bj を結び,道j の長さがC j であることを表す.
   地点Aj は地点Bj より高度が低い地点であり,道j は地点Aj から地点Bj への一方通行となるもの
   とする.必ずAj , Bj であり,また,Aj = Ak かつBj = Bk なる道k (k , j) は存在しない.


出力

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


採点基準

 以下,チェックポイントの数をK とおく.すなわち,K = S 1 + S 2 + · · · + S N である.
 採点用データのうち,配点の30%分については,K ≦10 を満たす.
 採点用データのうち,配点の30%分については,N ≦100 かつM ≦500 を満たす.
 採点用データのうち,配点の10%分については,これら2 つの条件の両方を満たす.
 採点用データのうち,配点の50%分については,これら2 つの条件の少なくとも一方を満たす.





                   オリエンテーリング– 2 / 4

Japanese Olympiad in Informatics 2010/2011
                                                                                    Qualifying Trial
                                                             April 23–24, May 3–5, 2011, Tokyo/Osaka

                                                                      Contest Day 4 – Orienteering


入出力の例

 入力例         出力例

 8 12                 29
 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


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





                   オリエンテーリング– 3 / 4

Japanese Olympiad in Informatics 2010/2011
                                               Qualifying Trial
                       April 23–24, May 3–5, 2011, Tokyo/Osaka

                                  Contest Day 4 – Orienteering



     8

          3

            5

      3        7

         8      3


     2           2      6


                7

  7  8       4  9

    6          4

       5     5

         1





オリエンテーリング– 4 / 4