信息
- ID
- 87
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
对于 30% 的数据,K≤10。
直接爆搜即可。
对于 30% 的数据,K≤100000。
设 f[i][j] 表示通过 i 米 走到 j 是否可行,枚举下一步转移
时间复杂度 O(K)。
取 w=min(d1,2,d2,3),那么对于每一种方案,均可以通过往返跑 w 这条边,来让距离增加 2w。
也就是说,如果存在距离为 k 的方案,那么必然存在距离为 k+2w 的方案。
设 dis[i][j] 表示从起点出发到达 i,距离模 2w 为 j 时的最短路。
把每个点拆成 2w 个跑 dijkstra 即可得到 dis 数组
根据 dis[2][j] 解不等式即可得到最优路线。
时间复杂度 O(wlogw)