← 返回题目列表

AtCoder · joiopen2022_c

C. 学校路

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

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

通学路 (School Road) - 原题 PDF 第 1 页
原题PDF第1页
通学路 (School Road) - 原题 PDF 第 2 页
原题PDF第2页
通学路 (School Road) - 原题 PDF 第 3 页
原题PDF第3页
通学路 (School Road) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                          schoolroad

                  通学路(School Road)



 ビーバーランドはN 個の都市からなり,都市には1 からN までの番号が付いている.都市と都市を結ぶ
道はM 個あり,道には1 からM までの番号が付いている.道i (1 ≦i ≦M) は都市Ai と都市Bi を双方向
に結んでおり,その長さはCi である.どの都市からどの都市へも何本かの道を通ることで移動できる.
 都市1 に住んでいるビーバーのビ太郎は,都市N にある学校に通っている.ビ太郎は,いつもある決まっ

た通学路を通って学校に通っている.通学路とは以下のようなものである.

    • 都市1 と都市N の間の最短距離をL とする.

    • 通学路は,都市1 と都市N を結ぶ,長さL の移動経路である.

 今日はとても天気が良いので,ビ太郎は普段より遠回りして下校することにした.すなわち,都市N か

ら都市1 へ長さがL よりも長い経路を通って下校する.ただし,ビ太郎は飽きっぽい性格であるため,同

じ地点を複数回訪れないようにしたい.つまり,同じ都市を複数回訪れたり,道の途中で引き返したりする

ことのないように下校したい.

 ビーバーランドの都市と道の情報が与えられたとき,このような下校経路が存在するかどうかを判定する

プログラムを作成せよ.


入力


 入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.


    N M

      A1 B1 C1
      A2 B2 C2
                                 ...

     AM BM CM


出力

 標準出力に,長さがL より長く同じ地点を複数回訪れないような下校経路が存在するならば1 を,存在

しないならば0 を出力せよ.





                        通学路– 1 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                  JOI Open Contest

                                                                                      July 3, 2022


                                                                          schoolroad



制約

    • 2 ≦N ≦100 000.

    • 1 ≦M ≦200 000.
    • 1 ≦Ai < Bi ≦N (1 ≦i ≦M).
    • 1 ≦Ci ≦1 000 000 000 (= 109) (1 ≦i ≦M).
    • どの都市からどの都市へも何本かの道を通ることで移動できる.


小課題

    1. (7 点) M ≦40.

    2. (15 点) N ≦18.

    3. (23 点) M −N ≦13.

    4. (35 点) すべての相異なる都市a, b, c について,都市a から都市b を通らず都市c に移動する経路が

   存在する.

    5. (20 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   4 4                            0

   1 2 1

   1 3 2

   2 4 4

   3 4 3

 この例では,ビ太郎の住んでいる都市1 と学校のある都市4 の間の最短距離は5 である.

 同じ地点を複数回訪れないような下校経路には以下の2 通りがある.

    • 道3 →1 の順に通って都市4 →2 →1 と移動する長さ5 の経路

    • 道4 →2 の順に通って都市4 →3 →1 と移動する長さ5 の経路

 長さが5 より長く同じ地点を複数回訪れないような下校経路は存在しないので,0 を出力する.

 この入力例はすべての小課題の制約を満たす.





                        通学路– 2 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                JOI Open Contest

                                                                                    July 3, 2022


                                                                         schoolroad


 入力例2              出力例2

 4 4                            1

 1 2 1

 1 3 3

 2 4 4

 3 4 3

この例では,ビ太郎の住んでいる都市1 と学校のある都市4 の間の最短距離は5 である.

同じ地点を複数回訪れないような下校経路には以下の2 通りがある.

  • 道3 →1 の順に通って都市4 →2 →1 と移動する長さ5 の経路

  • 道4 →2 の順に通って都市4 →3 →1 と移動する長さ6 の経路

長さが5 より長く同じ地点を複数回訪れないような下校経路が存在するので,1 を出力する.

この入力例はすべての小課題の制約を満たす.


 入力例3              出力例3

 3 4                            0

 1 2 1

 1 2 2

 1 3 3

 1 3 3

この入力例は小課題1, 2, 3, 5 の制約を満たす.


 入力例4              出力例4

 4 5                            1

 1 2 1

 1 3 2

 2 4 4

 3 4 3

 2 3 1

この入力例はすべての小課題の制約を満たす.





                       通学路– 3 / 4

The 21st Japanese Olympiad in Informatics (JOI 2021/2022)

                                                                JOI Open Contest

                                                                                    July 3, 2022


                                                                         schoolroad


 入力例5              出力例5

 12 17                          0

 2 4 656247308

 4 6 106088453

 1 5 754343261

 9 12 497827261

 3 8 759830309

 3 4 61084725

 1 6 324702188

 3 6 415317430

 7 12 846175092

 5 8 278621369

 1 10 891247646

 10 12 755236904

 6 8 511967203

 5 6 597197970

 1 7 800309458

 7 9 348347831

 10 11 134217757

この入力例は小課題1, 2, 3, 5 の制約を満たす.





                       通学路– 4 / 4