关于dij的写法
查看原帖
关于dij的写法
375208
LawrenceSivan楼主2021/6/7 16:50

请问这两种写法完全等价吗?

while (!q.empty()) {
	w = q.top().dis, u = q.top().x, q.pop();
	if (vis[u]) continue;
	vis[u]=true;
	for (int i = he[u]; i; i = ne[i]) {
		v = to[i];
		if (dis[v] >= dis[u] + val[i]) {
			dis[v] = dis[u] + val[i];
			q.push(node(dis[v], v));
		}
	}
}
while (!q.empty()) {
	w = q.top().dis, u = q.top().x, q.pop();
	if (dis[u] != w) continue;
	for (int i = he[u]; i; i = ne[i]) {
		v = to[i];
		if (dis[v] >= dis[u] + val[i]) {
			dis[v] = dis[u] + val[i];
			q.push(node(dis[v], v));
		}
	}
}
2021/6/7 16:50
加载中...