7K12 blog

猫でも分かる何か

NyaaLIB::GTL_BFS

BFS(幅優先探索)計算量  O(V+E)

  • BFS開始頂点は複数になることも多いので配列を渡す
  • 昇順に頂点を遷移したいときは queue を priority_queue にする
std::queue<long long> q; → std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq;
#include <bits/stdc++.h>

namespace NyaaLIB
{
	struct BFS_ARG
	{
		using vl = std::vector<long long>;
		using wgraph = std::vector<std::vector<std::pair<long long, long long>>>;
		using umlb = std::unordered_map<long long, bool>;
		vl& start; wgraph& g; umlb& visited; vl& dp;
	};

	auto GTL_BFS = [&](BFS_ARG a)
	{
		std::queue<long long> q;
		for (auto& e : a.start) q.push(e), a.visited[e] = true;
		while (!q.empty())
		{
			long long now = q.front(); q.pop();
			for (auto& [next, cost] : a.g[now])
			{
				if (a.visited[next]) continue;
				a.visited[next] = true, q.push(next);
			}
		}
	};
}

実装例
https://atcoder.jp/contests/abc244/submissions/31391288