算竞代码设计与技巧解析：

本文使用了 ai 辅助，旨在更好的帮助大家理解一些技巧

以这一题为例，需要对节点 1 求两次 dijkstra，怎么使得代码写的简洁？ ac 代码如下，我们来一一解析：

void solve()
{
	int n(q_), m(q_);
	using ED = array<int, 2>;
	using GRAPH = vector<vector<ED>>;

	GRAPH tr(n + 1);
	GRAPH rtr(n + 1);
	ffp(i, 1, m)
	{
		int u(q_), v(q_), w(q_);
		tr[u].push_back({ w,v });//tr是树边，本人的习惯
		rtr[v].push_back({ w,u });//rtr是反图
	}

	auto dij = [&](int st, GRAPH& gp)->ll
		{
			priority_queue<ED, vector<ED>, greater<ED>>dui;
			vector<int>dis(n + 1, iINF); dis[st] = 0;

			dui.push({ 0,st });
			while (dui.size())
			{
				auto [w, now] = dui.top();
				dui.pop();
				if (dis[now] < w)continue;
				for (auto [nxtw, nxt] : gp[now])
				{
					if (nxtw + dis[now] >= dis[nxt])continue;
					dis[nxt] = nxtw + dis[now];
					dui.push({ nxtw + dis[now],nxt });
				}
			}
			return accumulate(dis.begin() + 1, dis.end(), 0ll);
		};
	cout << dij(1, tr) + dij(1, rtr) << endl;
	return;
}

【初始化与快读】 首先，我们使用 n(q_), m(q_) 对变量进行初始化。这里的 q_ 是封装好的快读对象（Fast I/O），用于高效读取整数。值得一提的是，n(q_) 使用的是直接初始化（Direct Initialization），而我们常见的 n = q_ 属于复制初始化（Copy Initialization）。虽然在基础类型上二者生成的汇编指令并无差异，但直接初始化更具 Modern C++ 的风格。

【类型别名优化】 为了提升代码的可读性与编写效率，我们使用 using ED = array<int, 2> 为边的存储结构定义别名，同理定义了 GRAPH。这样不仅减少了冗余代码，也便于后续维护。

【存图细节】 在读入边权并建图时，有一个关键细节：tr[u].push_back({ w, v })。请注意，我们将权值 w 放在了 array 的首位。这是为了配合后续的 priority_queue。由于 STL 的容器默认按字典序比较（即先比较第一个元素），将权值置于首位，可以直接利用默认的比较规则实现“按权值排序”，无需额外编写比较函数。

【Dijkstra 的封装】 我们使用 Lambda 表达式封装了 Dijkstra 算法。在传参时，图结构 GRAPH 必须使用引用传递（建议为 const 引用），以避免在函数调用时发生巨大的内存拷贝开销，防止 TLE（超时）。

【累加器的陷阱】 计算最终结果时，我使用了 <numeric> 库中的 accumulate 函数。这里潜藏着一个常见的溢出陷阱：accumulate 的第三个参数决定了累加过程的数据类型。如果传入 0，编译器会将其推导为 int 类型进行累加，这在处理大数时会导致溢出。因此，必须显式传入 0ll（即 long long 类型的 0），以确保计算过程使用长整型。

【I/O 细节】 最后，输出时使用 \n 替代 endl。endl 会强制刷新缓冲区，在大规模输出场景下可能导致显著的性能损耗。

算竞代码设计与技巧解析：

全站热榜

创作者周榜