P6924 [ICPC 2016 WF] Road Times

5 秒，1024 MB Ubol Narongdid 是一家名为 Special D-Liver-E 的新兴初创公司的创始人。她想要垄断普吉岛地区医院之间的器官隔夜递送市场。为了安排计划，准确估计执行这些递送所需的时间非常重要。已经在一些医院之间进行了多次递送，因此这些医院对之间的递送时间是已知的。公司目前有软件来估计其他（尚未旅行过的）行程的时间，但到目前为止，所有的估计都非常不准确。 你被要求提出一种方法来改善这些估计。你可以使用以下信息：1）普吉岛地区每对城市之间连接道路的长度（以公里为单位），以及 2）一组先前执行的各种递送的时间（以分钟为单位）。 你知道道路是单向的，每条道路都有一个固定的速度限制，介于 $30$ 到 $60$ 公里每小时之间。速度限制是实数，不必是整数。你还知道递送卡车总是选择最小化行驶距离的路线，并且在每条道路上总是以等于该道路速度限制的恒定速度行驶。因此，例如，如果某次旅行是 $50$ 公里，所需时间在 $50$ 到 $100$ 分钟之间（包括边界），在没有其他信息的情况下。但你确实有其他信息，即先前递送的时间。你需要利用这些信息来产生尽可能好的估计。

无

无

时间限制：5000 毫秒，内存限制：1048576 kB。 国际大学生程序设计竞赛（ACM-ICPC）世界总决赛 2016。 题面翻译由 ChatGPT-4o 提供。