萌新对于结论的疑惑
查看原帖
萌新对于结论的疑惑
552165
ComplexPlanck楼主2022/8/1 21:35

RT,对于那个建正反图跑两次 Dijkstra 的做法,只用边更新而不用点更新也能 AC ,那么只用边更新是对的吗?/yiw

// oes[] 是原图的边
for (int i = 1; i <= m; ++ i)
	if (frm[oes[i].u] != gto[oes[i].v])
		ans = std::min(ans, f[oes[i].u] + weight[i] + g[oes[i].v]);
// 用边更新答案
for (int i = 1; i <= n; ++ i)
	if (frm[i] != gto[i])
		ans = std::min(ans, f[i] + g[i]);
// 用点更新答案
2022/8/1 21:35
加载中...