1 条题解

  • 0
    @ 2026-11-15 13:03:24

    题目分析

    首先能看出这是一道最短路题目。由于最终所有流浪猫都要聚集到点 11,我们用 Dijkstra 求出每个点到点 11 的最短路径。注意题目要求时间相同时选择编号字典序较小的路径,因此需要额外按编号顺序处理,保证得到的是一棵满足字典序要求的最短路径树。

    接下来考虑如何计算总时间。先假设不增加捷径:由于所有流浪猫走向点 11 的路径最终会形成一棵树,也就是最短路径树,我们可以直接建出这棵树,在树上求解总时间。

    求解总时间有两种方法:一是对于每个点,求出它到点 11 的距离再对 cic_i 加权求和;二是考虑最短路径树上的每一条边,求出经过这条边的流浪猫总数,也就是该边对应子树内的猫的数量。此处第二种方式更利于后续分析。

    现在考虑如何增加捷径。沿用上面的第二种方式:当子树 ii 内的所有流浪猫都汇聚在点 ii 时,如果在 11 与 ii 之间建一条通行时间为 tt 的捷径,那么每只猫可以少走 disi−tdis_i - t 的时间,其中 disidis_i 表示点 ii 到点 11 的最短距离。于是枚举所有点 ii,求出节省时间的最大值即可。

    需要注意题目中的细节:流浪猫只有在常规路径上"偶然发现"捷径、且捷径确实更快时才会改走捷径,因此节省量只在 disi>tdis_i > t 时为正,否则该点无法带来收益。

    • 1

    信息

    ID
    47
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    1
    已通过
    1
    上传者