关于带优 SPFA 和库里的 spfa_hack #128

Activity

1. weilycoder

   changed the title [-]关于 SPFA[/-] [+]关于 SPFA 和库里的 spfa_hack[/+] on Sep 30, 2024
2. weilycoder

   closed this as completedon Sep 30, 2024
3. weilycoder commented on Sep 30, 2024

   

   weilycoder

   on Sep 30, 2024

   Last edited by weilycoder

   ContributorAuthor

   More actions

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

   shuffle 用的这个 pr 的版本 #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;
   }
4. weilycoder

   changed the title [-]关于 SPFA 和库里的 spfa_hack[/-] [+]关于带优 SPFA 和库里的 spfa_hack[/+] on Sep 30, 2024
5. weilycoder

   reopened this on Sep 30, 2024