#PQJ1551x410. QOJ 1551_410

    ID: 2656 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2021 集训最短路

QOJ 1551_410

Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Telegraph 電報(Telegraph) JOI 諸島は太平洋に浮かぶ小さな島国である.JOI 諸島にはN 個の島があり,1 からN までの番号が付 けられている. JOI 諸島では島同士の通信は主に無線によって行われる.それぞれの島には電波の送信機と受信機がひ とつずつある.送信機は全方向に電波を送ることができるが,受信機は特定の方向からの電波しか受け取 ることができない.そのため,それぞれの受信機は,特定のひとつの島からの電波しか受け取ることがで きない.ただし,受信機の向きを変えることで,どの島からの電波を受け取ることができるかを変えるこ とができる. 現在,島i (1 ≦i ≦N) の受信機は島Ai (Ai , i) からの電波を受け取ることができる.また,島i の受信 機の向きを変えるのにかかるコストは,どう向きを変えるかによらず,Ci である. JOI 諸島では,公共事業として電報サービスを行っている.島i (1 ≦i ≦N) からの電波を島j (1 ≦j ≦ N, j , i) の受信機が受け取ることができるとき,島i から島j に無線通信によって電報を送ることができる. また,電報はいくつかの島を経由して送ってもよい.すなわち,島i,島j,島k (1 ≦i, j, k ≦N かつi, j, k はそれぞれ相異なる) について,島i から島j に電報を送ることができ,島j から島k に電報を送ることが できるとき,島i から島k に電報を送ることができる.無線通信以外の方法で電報を送ることはできない. JOI 諸島の逓信大臣であるあなたは,任意の島から任意の島へ電報を送れるようにしたい.そのために は,いくつかの島の受信機の向きを変える必要があるかもしれない.いくつかの島の受信機の向きを変え るのにかかるコストは,それぞれの受信機の向きを変えるのにかかるコストの総和である. 任意の島から任意の島へ電報を送れるようにするためにかかるコストの最小値を計算せよ. 課題 JOI 諸島の島の数と,それぞれの島の受信機に関する情報が与えられたとき,任意の島から任意の島に 電報を送れるようにするためにかかるコストの最小値を求めるプログラムを作成せよ. 入力 標準入力から以下のデータを読み込め. • 1 行目には,整数N が書かれている.これは,JOI 諸島にはN 個の島があることを表す. • 続くN 行のうちのi 行目(1 ≦i ≦N) には,整数Ai,Ci が空白を区切りとして書かれている.これは, 島i の受信機は,現在,島Ai からの電波を受け取ることができ,向きを変えるのにかかるコストが Ci であることを表す. 電報– 1 / 3 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Telegraph 出力 標準出力に,任意の島から任意の島に電報を送れるようにするためにかかるコストの最小値を1 行で出 力せよ. 制限 すべての入力データは以下の条件を満たす. • 2 ≦N ≦100 000. • 1 ≦Ai ≦N (1 ≦i ≦N). • Ai , i (1 ≦i ≦N). • 1 ≦Ci ≦1 000 000 000 (1 ≦i ≦N). 小課題 小課題1 [10 点] • N ≦10 を満たす. 小課題2 [30 点] • N ≦15 を満たす. 小課題3 [30 点] • N ≦3 000 を満たす. 小課題4 [30 点] 追加の制限はない. 電報– 2 / 3 Japanese Olympiad in Informatics 2015/2016 Spring Training Camp/Qualifying Trial March 19–25, 2016, Komaba/Yoyogi, Tokyo Contest Day 3 – Telegraph 入出力例 入力例1 出力例1 4 4 2 2 1 4 1 3 3 1 島2 の受信機の向きを変え,島4 からの電波を受け取れるようにする.すると任意の島から任意の島へ 電報を送れるようになり,かかったコストは4 である. どのように受信機の向きを変えてもコストが4 を下回ることはないので,4 を出力する. 入力例2 出力例2 4 5 2 2 1 6 1 3 3 1 まず,島1 の受信機の向きを変え,島4 からの電波を受け取れるようにする.次に,島3 の受信機の向 きを変え,島2 からの電波を受け取れるようにする.すると任意の島から任意の島へ電報を送れるように なり,かかったコストは2 + 3 = 5 である. どのように受信機の向きを変えてもコストが5 を下回ることはないので,5 を出力する. 入力例3 出力例3 4 4 2 2 1 3 4 2 3 3 島1 と島3 の受信機の向きを変えればよい. 入力例4 出力例4 3 0 2 1 3 1 1 1 どの島の受信機の向きも変えなくてよい. 電報– 3 / 3