1 条题解

  • 0
    @ 2026-11-15 14:07:04

    题目分析

    30 pts

    对于 30%30\% 的数据,K≤10K \le 10。

    直接爆搜即可。

    60 pts

    对于 30%30\% 的数据,K≤100000K \le 100000。

    设 f[i][j]f[i][j] 表示通过 ii 米 走到 jj 是否可行,枚举下一步转移

    时间复杂度 O(K)O(K)。

    100 pts

    取 w=min⁡(d1,2,d2,3)w = \min(d_{1, 2}, d_{2, 3}),那么对于每一种方案,均可以通过往返跑 ww 这条边,来让距离增加 2w2w。

    也就是说,如果存在距离为 kk 的方案,那么必然存在距离为 k+2wk+2w 的方案。

    设 dis[i][j]dis[i][j] 表示从起点出发到达 ii,距离模 2w2w 为 jj 时的最短路。

    把每个点拆成 2w2w 个跑 dijkstradijkstra 即可得到 disdis 数组

    根据 dis[2][j]dis[2][j] 解不等式即可得到最优路线。

    时间复杂度 O(wlog⁡w)O(w \log w)

    • 1

    信息

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