Day 8 讲义：BFS、Dijkstra 与状态图

图题先别急着画边。先问：

一个“状态”是什么？
从一个状态能怎样到另一个状态？
每条边代价是多少？

状态和转移一旦明确，BFS 或 Dijkstra 往往自然出现。

1. BFS：为什么第一次到达就是最短

普通队列按距离一层一层扩展：

距离 0 的点先出队；
再处理距离 1；
再处理距离 2。

因此一个点第一次被访问时，得到的就是最短边数。

1.1 模板

queue<int> q;
memset(dis, -1, sizeof dis);
dis[s] = 0;
q.push(s);

while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int v: g[u]){
        if(dis[v] != -1) continue;
        dis[v] = dis[u] + 1;
        q.push(v);
    }
}

dis[v] != -1 同时表示“访问过”和“距离已确定”。

2. Dijkstra：每次确定当前最近点

边权不相等时，BFS 的队列顺序不再可靠。Dijkstra 用小根堆，每次取当前距离最小的未确定状态。

priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> pq;
vector<long long> dis(n + 1, INF);
dis[s] = 0;
pq.push({0, s});

while(!pq.empty()){
    auto [d, u] = pq.top();
    pq.pop();
    if(d != dis[u]) continue; // 堆里的旧记录

    for(auto [v, w]: g[u]){
        if(dis[v] > d + w){
            dis[v] = d + w;
            pq.push({dis[v], v});
        }
    }
}

前提：边权不能为负。 有负边时，“当前最小”以后仍可能被更短路径更新，Dijkstra 的正确性失效。

3. 520B：数字也是图上的点

从 n 变到 m，每一步可做：

x -> 2x
x -> x-1

数字 x 就是一个节点，两种操作就是边。所有边权为 1，所以用 BFS。

为了防止无限扩展，设一个安全上界。常用上界是：

0 <= x <= 2*max(n,m)+10

因为超过目标很多再继续翻倍不会更优。

4. 多源 BFS：所有起点一起入队

35C 中有多个火源。把所有火源的距离设为 0，一起入队：

for(每个火源){
    dis[x][y] = 0;
    q.push({x, y});
}

之后正常 BFS。一个格子第一次被哪个火源到达不重要，第一次到达的时间一定最早。

多源 BFS 的本质不是“跑很多次 BFS”，而是新增一个虚拟源点连向全部起点。

5. 1106D：BFS 的队列换成最小堆

若题目要求在所有合法 BFS 序中输出字典序最小的一种，距离层次仍由 BFS 决定，但同一层内应该优先访问编号小的点。

做法：把普通队列换成小根堆。

仍然是无权最短路；
只是同距离状态的处理顺序改成最小编号优先。

6. 601A：补图也能 BFS

一条路线走原图，另一条走补图。先判断起点终点是否在原图直接相连：

若原图有边，原图路线不能作为答案的一条；
若原图无边，补图路线不能作为答案的一条。

对需要的图做 BFS。补图不一定要真的建出所有边；小规模时邻接矩阵可直接判断，大规模时要设计未访问集合。

7. 954D：双向距离预处理

问“加一条不存在的边后，最短路是否仍不变”。先从起点、终点各跑一次 BFS：

ds[u] = s 到 u 的最短距离
dt[u] = u 到 t 的最短距离

若加边 (u,v)，新路径可能是：

ds[u] + 1 + dt[v]
ds[v] + 1 + dt[u]

两者都不小于原最短路，才可以安全加边。

这是典型技巧：很多“加一条边”的题，先把两端到所有点的距离预处理。

8. 1037D：验证给定 BFS 序

验证题不要真的“照序列走一遍”就结束。正确做法：

1. 记录给定序列中每个点的排名；
2. 把每个点邻居按排名排序；
3. 从 1 开始跑一次标准 BFS；
4. 比较得到的序列和给定序列。

原因：合法 BFS 的自由度只在“同一层邻居的入队顺序”。按给定排名排序后，若它真合法，标准 BFS 就能复现它。

9. 易错点

• BFS 只适用于所有边权相同；
• Dijkstra 弹堆后要跳过旧记录；
• 多源 BFS 的所有源点距离都应初始化为 0；
• 图不连通时，dis 可能仍是 -1 或 INF；
• 状态图要先证明搜索范围足够且有限。

10. 今日口诀

状态先定边再连，边权决定用什么。
等权一层层 BFS，非负权堆跑 Dijkstra。
多个起点一起推，双端距离先预处理。
验证序列排邻居，复现一遍见真假。