← 返回题目列表

AtCoder · joisc2009_ski

ski. 滑雪

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

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

スキー (Ski) - 原题 PDF 第 1 页
原题PDF第3页
スキー (Ski) - 原题 PDF 第 2 页
原题PDF第4页
可复制的 PDF 提取文本
Ski: スキー


input ファイル“ski.in”
output 標準出力
ソースファイルski.c/ski.cpp
時間制限1 秒/ データ


  JOI 氏はスキー場として有名なIOI 高原でホテルIOI を経営している.IOI 高原はとても複雑

な地形をしておりスキー上級者にとても人気があるのだが,その複雑な地形ゆえに初心者にあ

まり優しいとは言えない.しかし,JOI 氏は初心者にもこのIOI 高原の良さをわかって欲しい

と思っている.

 そこで最も易しいコースを見つけ出し,そのコースでIOI 高原を初心者向けに宣伝したいと

思っている.ここで言う最も易しいコースというのは平均速度(つまり全行程の距離をかかった

時間で割って出る速度) が最も低いコースである.ただし,JOI 氏はホテルIOI を是非利用して

もらいたいので,コースの始点は必ずホテルIOI から直接出ているリフトで行くことのできる

地点にし,コースの終点は必ずホテルIOI にしなければならない.

  IOI 高原の各地点には標高が高いほど小さい番号が割り振られることになっている.また,標

高が同一の地点はないものとして考えて良く,高い地点からより低い地点にしか進まないと考

えて良いので,ある地点から同じ地点に戻ることはできないと考えられる.

 コースとして使える道筋とその道のり,その区間平均速度およびホテルIOI からリフトで行

くことのできる地点が与えられたとき,最も易しいコースの平均速度を求め,その平均速度の

小数第一位を四捨五入した整数を出力するプログラムを作成せよ.


Input. 入力ファイルはski.in である.1 行目には地点番号の最大値であるとともにホテルIOI

の地点を表す正整数n (1 ≦n ≦10000) と,ホテルIOI からリフトで行くことのできる地点の数

を表す正整数m (1 ≦m < n),コースとして使える道筋の本数を表す正整数c (1 ≦c ≦100000)

の3 つが空白区切りで書かれている.

  2 行目にはホテルIOI からリフトで行くことのできる地点を表す正整数ai (1 ≦i ≦m, 1 ≦

ai < n) がm 個,空白区切りで書かれている.

  3 行目以降の第j + 2 行目(1 ≦j ≦c) の各行には,コースとして使うことのできる道筋の始

点の地点番号を表す正整数fj と終点の地点番号を表す正整数tj (1 ≦fj < tj ≦n),その道筋

の始点から終点までの道のりの長さを表す正整数dj (1 ≦dj ≦100),その道筋を通る場合に出

る平均速度を表す正整数sj (1 ≦sj ≦100000) の4 つが空白区切りで書かれている.

 採点に使われるどの入力においても,最も易しいコースの平均速度からの誤差が0.01 以内の

値を小数第一位で四捨五入した結果は同一の整数になることが保証される.また,採点に使わ

                          スキー–1/2

れるどの入力においても,ホテルIOI から直接出ているリフトで行くことのできる地点が始点

でホテルIOI が終点であるコースが存在することが保証される.


Output. 出力は標準出力に行うこと.小数第一位を四捨五入した最も易しいコースの平均速

度を整数で出力せよ.

採点基準採点用データのうち,配点の20% 分については,n ≦10, c ≦100 を満たし,配点

の50% 分については,n ≦100, c ≦100 を満たす.


例1
 ski.in   標準出力
 3 1 3       1250
 1
 1 2 6 1000
 2 3 4 2000
 1 3 3 3000

例2
 ski.in   標準出力
 4 2 5       3261
 1 2
 1 3 2 5000
 1 3 9 4000
 2 3 3 5000
 2 4 4 7000
 3 4 8 3000





                          スキー–2/2