时间复杂度
O(n)，n是边数。
使用前提
边的权只有两种:0,1。
典型场景
n个端点的无向图，编号范围[0,n)。Edges0表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有路联接。Edges1表示{{n1,n2},...{n3,n4}}表示n1和n2，n3和n4之间有损坏的路连接。要想让s和d之间至少有一条通道,最小需要维修多少条路。如果无法到达，请返回-1。可能有环，但无自环，重边，可能不联通。
解题思路
可以用类似上章的思路，没损害的路加到pre中，损坏的路加到que中。距离相等的点，谁先谁后无所谓。需要维修的路入队的时候不能计算最短距离，因为不一定是最短边。改在入队计算最短距离，第一层循环记录最短距离。
核心代码
class CBFS1 { public: CBFS1(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s) { m_vDis.assign(vNeiB0.size(), -1); //m_vDis[s] = 0; queue<int> pre; pre.emplace(s); for (int i = 0; pre.size(); i++) { queue<int> dp; while (pre.size()) { const int cur = pre.front(); pre.pop(); if (-1 != m_vDis[cur]) { continue; } m_vDis[cur] = i; for (const auto next : vNeiB0[cur]) { pre.emplace(next); } for (const auto next : vNeiB1[cur]) { dp.emplace(next); } } dp.swap(pre); } } public: vector<int> m_vDis; };
测试样例
#define CBFS CBFS1 class CDebugBFS : public CBFS { public: using CBFS::CBFS; void Assert(const vector<int>& vDis) { for (int i = 0; i < vDis.size(); i++) { assert(vDis[i] == m_vDis[i]); } } }; struct CDebugParam { int n; vector<vector<int>> edges0; vector<vector<int>> edges1; int s; vector<int> dis;//答案 }; int main() { vector<CDebugParam> params = { {1,{},{},0,{0}},{2,{},{},0,{0,-1}},{2,{{0,1}},{},0,{0,0}},{2,{},{{0,1}},0,{0,1}}, {6,{}, { {0,1},{1,2},{1,3},{2,4},{4,5},{3,5}},0,{0,1,2,2,3,3} }, {6,{{3,5}}, { {0,1},{1,2},{1,3},{2,4},{4,5}},0,{0,1,2,2,3,2} } }; for (const auto& par : params) { auto vNeiB0 = EdgeToNeiBo(par.n, par.edges0); auto vNeiB1 = EdgeToNeiBo(par.n, par.edges1); CDebugBFS bfs(vNeiB0, vNeiB1,par.s); bfs.Assert(par.dis); } }
类似场景
魔塔经典问题，砸墙需要一个锄头，没墙的地方可以随便移动，如果用尽可能少的锄头到达目的地。许多游戏经过箭塔附件时，会遭到箭塔攻击。如何已最小的损坏通过箭塔。
用双向队列优化
当前状态 |
操作 |
新状态 |
空 |
处理结束 |
|
首尾入队 |
一种最短距离 |
|
一种最短距离 |
出队 |
状态不变或变为空 |
队首入队 |
一种最短距离或两种最短距离 |
|
队尾入队 |
一种最短距离或两种最短距离 |
|
二种最短距离 |
出队 |
状态不变或变为一种最短距离 |
队首入队 |
两种最短距 |
|
队尾入队 |
两种最短距 |
|
class C01BFSDis { public: C01BFSDis(vector<vector<int>>& vNeiB0, vector<vector<int>>& vNeiB1, int s) { m_vDis.assign(vNeiB0.size(), -1); std::deque<std::pair<int,int>> que; que.emplace_back(s,0); while (que.size()) { auto it = que.front(); const int cur = it.first; const int dis = it.second; que.pop_front(); if (-1 != m_vDis[cur]) { continue; } m_vDis[cur] = it.second; for (const auto next : vNeiB0[cur]) { if (-1 != m_vDis[next]) { continue; } que.emplace_front(next,dis); } for (const auto next : vNeiB1[cur]) { if (-1 != m_vDis[next]) { continue; } que.emplace_back(next, dis+1); } } } public: vector<int> m_vDis; };
下载
源码下载：
https://download.csdn.net/download/he_zhidan/88383828
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17 或Win10 VS2022 Ck++17
相关下载
算法精讲《闻缺陷则喜算法册》doc版
