← 返回题目列表

AtCoder · joisc2010_finals

finals. 决赛场地(决赛)

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

以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。

本選会場 (Finals) - 原题 PDF 第 1 页
原题PDF第1页
本選会場 (Finals) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                             Contest day 3 - Finals

                      本選会場(Finals)


  JOI 国にはN 個の都市があり,1 からN の番号がついている.また,M 本の道路がある.全ての道路は
異なる2 つの都市を結び,双方向に通行可能である.JOI 国の任意の2 つの都市は,道路をたどって片方か
らもう片方へ到達可能である.JOI 国の道路は全て有料道路であり,道路ごとに通行料金が決まっている.
  JOI 国でも情報オリンピックは開催される.JOI 国の情報オリンピックの本選には,各都市の代表選手が
出場する.本選をどの都市で開催するかを決定し,選手をそれらの都市に集めるためにかかる金額を見積
もっておく必要がある.本選はK 個の都市で開催し,本選の際には全ての選手をそれらのいずれかの都市
に移動させなければならない.1 つの都市に集まる選手の人数に制限はない.
 本選を開催する都市に選手を集める際には,道路を利用する.通行料金がc の道路は,一度に何人で通
行しても料金はc である.そこで,選手を移動させる順番を工夫することによって,複数の選手を一度に
通行させるようにすれば,料金を節約することができる.
 本選を開催する都市を決定し,選手を本選会場に集める際にかかる通行料金の和を最小化したい.

課題(TASK)

  N, M, K と全ての道路の情報が与えられたとき,選手を本選会場に集める際にかかる通行料金の和の最小
値を計算するプログラムを作成せよ.

制限(CONSTRAINTS)
   1 ≦N ≦100, 000 都市の数
   1 ≦M ≦100, 000 道路の数
   1 ≦K ≦N    本選を開催する都市の個数
   1 ≦Ai < Bi ≦N  道路i の結ぶ2 つの都市
   1 ≦Ci ≦100    道路i の通行料金

入力(INPUT)

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

   • 1 行目には整数N, M, K が空白を区切りとして書かれている.

   • 続くM 行には,1 行につき1 つの道路について記述されている.これらの行のうちのi 行目は道路i
   について記述しており,整数Ai, Bi,Ci が空白を区切りとして書かれている.

出力(OUTPUT)
 標準出力に選手を本選会場に集める際にかかる金額の最小値を表す1 つの整数を出力せよ.


                                                                                    Page 1 of 2

Japanese Olympiad In Informatics 2009/2010
                                                                          Spring Training Camp
                                              March 19 - 25, 2010, Komaba/Yoyogi, Tokyo

                                                                             Contest day 3 - Finals

採点基準(GRADING)
  40 点分のテストグループにおいて,N ≦1, 000 である.
  40 点分のテストグループにおいて,K = 1 である.
  20 点分のテストグループは,これら2 つの条件の両方をみたす.
  60 点分のテストグループは,これら2 つの条件の少なくとも一方をみたす.

入出力例(EXAMPLE)
  入力例(Sample Input)  出力例(Sample Output)
   4 3 1               16
   1 2 2
   2 3 9
   2 4 5

 例えば,都市1 で本選を開催するとし,まず都市4 の代表選手を都市2 へ移動させ,次に都市3 の代表
選手を都市2 へ移動させ,都市2 に居る3 人の選手を都市1 へ移動させればよい.

  入力例(Sample Input)  出力例(Sample Output)
   5 6 2               12
   1 2 5
   1 3 3
   2 3 4
   2 5 7
   3 4 6
   4 5 5

 例えば,都市3 と都市4 で本選を開催するとし,都市1, 2 の代表選手は都市3 へ,都市5 の代表選手は
都市4 へ集めればよい.





                                                                                    Page 2 of 2