社区讨论

如果你用dijkstra且tle

P1119灾后重建参与者 3已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@mhizj5y3
此快照首次捕获于
2025/11/03 18:16
4 个月前
此快照最后确认于
2025/11/03 18:16
4 个月前
查看原帖
本题使用 Dijkstra 是可以通过的,我们需要加一个剪枝优化,如下所示:
CPP
while(!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] 表示到终点的最短距离

		// ......
}
这行代码能够在当前距离比最优解更长时终止,因为比已求出的最优解更长也就没有继续跑的必要了,实测峰值耗时 926926 ms,关闭同步流后峰值耗时 779779 ms。

回复

7 条回复,欢迎继续交流。

正在加载回复...