Correct But Exponential

To fix the negative-edge bug, a teammate deletes the visited array entirely and keeps only the lazy staleness check, so a vertex is allowed back out of the heap whenever its distance improves:

while (!q.empty()) {
    auto [d_v, v] = q.top(); q.pop();
    if (d_v != dist[v]) continue;        // stale entry, skip
    for (auto [to, w] : adj[v]) {
        if (dist[v] + w < dist[to]) {
            dist[to] = dist[v] + w;
            q.push({dist[to], to});      // may re-enter, even if popped before
        }
    }
}

The input graph has negative edges but no negative cycle. Which is true of this version?

It is correct only when every negative edge leaves the source, since then no already-finalised vertex can be improved later.

It now returns correct distances on any graph with no negative cycle, but it is no longer $O(E \log V)$ : there is a family of graphs on $V$ vertices that forces $\Theta(2^{V/2})$ relaxations. It is usually fast in practice, which is what makes the blow-up dangerous.

It is still wrong. The check d_v != dist[v] discards precisely the improved entries the negative edge produced, so the fix cancels itself out.

It is correct and still $O(E \log V)$ , because lazy deletion changes only which entries are skipped, never how many times a vertex is processed.