1-k bfs

(Updated: )
(1 min to read)

考虑一个单源最短路径问题，但是图的边权范围是1-k，k不大，那就可以用以下方法本质上在一个队列中同时最多只有k+1种不同的dis的取值，因此只需要用k+1个队列来维护即可，当前队列为空时，就循环移位找到下一个非空的队列即可复杂度为$O(nk+m)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
queue<int> q[K+1];
q[0].push(s);
d[s] = 0;
int idx = 0, inq = 1;
while(inq>0) {
  while(q[idx].empty()) idx = (idx+1)%(k+1);
  int u = q[idx].front(); q[dx].pop();
  inq--;
  if(vis[u]) continue;
  vis[u] = 1;
  for(auto it : G[u]) {
    int v = it.fi, w = it.se;
    if(d[v]>d[u]+w) {
      d[v] = d[u] + w;
      q[d[v]%(k+1)].push(v);
      ++inq;
    }
  }
}