社区讨论
如果你用dijkstra且tle
P1119灾后重建参与者 3已保存回复 7
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 7 条
- 当前快照
- 1 份
- 快照标识符
- @mhizj5y3
- 此快照首次捕获于
- 2025/11/03 18:16 4 个月前
- 此快照最后确认于
- 2025/11/03 18:16 4 个月前
本题使用 Dijkstra 是可以通过的,我们需要加一个剪枝优化,如下所示:
CPPwhile(!q.empty()){
int u=q.top().second,w=q.top().first;
q.pop();
if(d[u]!=w) continue;
if(w>d[e]) continue; // 剪枝优化,e 表示终点,w 表示到当前点的距离,d[e] 表示到终点的最短距离
// ......
}
这行代码能够在当前距离比最优解更长时终止,因为比已求出的最优解更长也就没有继续跑的必要了,实测峰值耗时 ms,关闭同步流后峰值耗时 ms。
回复
共 7 条回复,欢迎继续交流。
正在加载回复...