← 返回题目列表

AtCoder · s8pc_2_g

G. Road 和 N AtCoder 公司

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

問題文

Atcoder在运输公司中,N存在一个工厂。

217X年,在这家公司,1只有一个困扰,那就是公司之间不存在道路相连。

运输公司社长「这是大问题!!不马上修的话就糟了!!」

所以现在是时候开始计划了。

该公司涉及运输,因此产品必须快速地从农村运输到城市,从城市运输到农村。因此,如果您为您的公司创建专用路径,您将能够处理许多订单。

但是,需要在以下条件下创建道路。

  • 道路应笔直,尽可能提高运输卡车的限速。
  • 除工厂外,道路不应相交,因为分级交叉口会显着增加成本。
  • 除了提高所有专用道路的速度限制外,我们希望尽快将车辆运送到目标公司。 我会修尽可能多的路。
  • 假设有道路连接工厂。

然而,该公司不知道如何得出最优解。

公司要求你,一个优秀的程序员,找到最优的解决方案。找出可以修建的最大道路数量。

但是,必须严格遵守问题文本中的条件。

注:题文中的217X年是超时空世界的时间。这里的时间可以被认为是现在。