关于带优 SPFA 和库里的 spfa_hack

[weilycoder]

[weilycoder]

可能是没打乱点，也可能是因为没设成无向图，总之以下代码可以 Hack 不带优化的 spfa

shuffle 用的这个 pr 的版本 https://github.com/luogu-dev/cyaron/pull/130

import random
from cyaron.graph import *
from cyaron.io import *

random.seed(0)
st = 1


def node_shuffler(table):
    global st
    t = random.sample(table, k=len(table))
    st = t[0]
    return t


hack_spfa = IO(file_prefix="spfa", disable_output=True)
g = Graph.hack_spfa(int(1e6), weight_limit=int(1e3))

output = g.to_str(
    shuffle=True, node_shuffler=node_shuffler,
)

hack_spfa.input_writeln(len(g.edges) - 1, len(list(g.iterate_edges())), st)
hack_spfa.input_writeln(output)

但带优化的 spfa 仍然跑得飞起，有 Hack spfa 所有常见优化的计划吗？

附带优 spfa：

#include <cstdint>
#include <cstring>
#include <iostream>
#include <queue>
#include <vector>
#define INF 0x3f3f3f3f3f3f3f3fLL
using namespace std;

const int N = 1400000;
int n, m, s;
struct edge {
  int v;
  long long w;
};
vector<edge> gg[N];
bool vis[N];
long long dis[N], W;

int qlog2ll(long long x) { return 63 - __builtin_clz(x); }

long long isqrt_newton(long long n) {
  if (n < 0)
    return -1;
  if (n == 0)
    return 0;
  long long x = 1LL << (qlog2ll(n) >> 1);
  bool decreased = false;
  for (;;) {
    long long nx = (x + n / x) >> 1;
    if (x == nx || (nx > x && decreased))
      break;
    decreased = nx < x;
    x = nx;
  }
  return x;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n >> m >> s;
  for (int i = 0; i < m; ++i) {
    int u, v;
    long long w;
    cin >> u >> v >> w;
    gg[u].push_back({v, w});
    gg[v].push_back({u, w});
    W += w;
  }
  W = isqrt_newton(W);
  memset(dis, 0x3f, sizeof(dis));
  dis[s] = 0;
  deque<int> q;
  q.push_front(s);
  while (!q.empty()) {
    int t = q.front();
    q.pop_front();
    vis[t] = false;
    for (edge ed : gg[t]) {
      if (dis[ed.v] > dis[t] + ed.w) {
        dis[ed.v] = dis[t] + ed.w;
        if (!vis[ed.v]) {
          vis[ed.v] = true;
          if (dis[ed.v] - q.front() > W)
            q.push_back(ed.v);
          else
            q.push_front(ed.v);
          if (dis[q.front()] > dis[q.back()])
            swap(q.front(), q.back());
        }
      }
    }
  }
  for (int i = 1; i <= n; ++i)
    cout << (dis[i] == INF ? INT32_MAX : dis[i]) << (i == n ? "" : " ");
  return 0;
}