lc3650
Dijkstra求从0到n-1的单源最短路，邻接表构建时无向边双向权重不同（x→y为原权值，y→x为原权值2倍）
小根堆+懒更新实现最短路求解，到达终点时直接返回最短距离
class Solution {
public:
int minCost(int n, vector<vector<int>>& edges) {
vector<vector<pair<int, int>>> g(n); // 邻接表
for (auto& e : edges) {
int x = e[0], y = e[1], wt = e[2];
g[x].emplace_back(y, wt);
g[y].emplace_back(x, wt * 2);
}
vector<int> dis(n, INT_MAX);
// min heap(起点到节点 x 的最短路长度，节点 x)
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
dis[0] = 0; // 起点到自己的距离是 0
pq.emplace(0, 0);
while (!pq.empty()) {
auto [dis_x, x] = pq.top();
pq.pop();
if (dis_x > dis[x])
// x 之前出堆过
continue;
if (x == n - 1) // 到达终点
return dis_x;
for (auto& [y, wt] : g[x]) {
auto new_dis_y = dis_x + wt;
if (new_dis_y < dis[y]) {
dis[y] = new_dis_y;
// 更新 x 的邻居的最短路
// 懒更新堆：只插入数据，不更新堆中数据
// 相同节点可能有多个不同的 new_dis_y，除了最小的 new_dis_y，其余值都会触发上面的 continue
pq.emplace(new_dis_y, y);
}
}
}
return -1;
}
};
我悟了(
// 模板来源 https://leetcode.cn/circle/discuss/mOr1u6/
template<typename T, typename F>
class LazySegmentTree {
// 注：也可以去掉 template<typename T, typename F>，改在这里定义 T 和 F
// using T = pair<int, int>;
// using F = pair<int, int>;
// 懒标记初始值
const F TODO_INIT = 0; // **根据题目修改**
struct Node {
T val;
F todo;
};
int n;
vector<Node> tree;
// 合并两个 val
T merge_val(const T& a, const T& b) const {
return a + b; // **根据题目修改**
}
// 合并两个懒标记
F merge_todo(const F& a, const F& b) const {
return a + b; // **根据题目修改**
}
// 把懒标记作用到 node 子树（本例为区间加）
void apply(int node, int l, int r, F todo) {
Node& cur = tree[node];
// 计算 tree[node] 区间的整体变化
cur.val += todo * (r - l + 1); // **根据题目修改**
cur.todo = merge_todo(todo, cur.todo);
}
// 把当前节点的懒标记下传给左右儿子
void spread(int node, int l, int r) {
Node& cur = tree[node];
F todo = cur.todo;
if (todo == TODO_INIT) { // 没有需要下传的信息
return;
}
int m = (l + r) / 2;
apply(node * 2, l, m, todo);
apply(node * 2 + 1, m + 1, r, todo);
cur.todo = TODO_INIT; // 下传完毕
}
// 合并左右儿子的 val 到当前节点的 val
void maintain(int node) {
tree[node].val = merge_val(tree[node * 2].val, tree[node * 2 + 1].val);
}
// 用 a 初始化线段树
// 时间复杂度 O(n)
void build(const vector<T>& a, int node, int l, int r) {
Node& cur = tree[node];
cur.todo = TODO_INIT;
if (l == r) { // 叶子
cur.val = a[l]; // 初始化叶节点的值
return;
}
int m = (l + r) / 2;
build(a, node * 2, l, m); // 初始化左子树
build(a, node * 2 + 1, m + 1, r); // 初始化右子树
maintain(node);
}
void update(int node, int l, int r, int ql, int qr, F f) {
if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
apply(node, l, r, f);
return;
}
spread(node, l, r);
int m = (l + r) / 2;
if (ql <= m) { // 更新左子树
update(node * 2, l, m, ql, qr, f);
}
if (qr > m) { // 更新右子树
update(node * 2 + 1, m + 1, r, ql, qr, f);
}
maintain(node);
}
T query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) { // 当前子树完全在 [ql, qr] 内
return tree[node].val;
}
spread(node, l, r);
int m = (l + r) / 2;
if (qr <= m) { // [ql, qr] 在左子树
return query(node * 2, l, m, ql, qr);
}
if (ql > m) { // [ql, qr] 在右子树
return query(node * 2 + 1, m + 1, r, ql, qr);
}
T l_res = query(node * 2, l, m, ql, qr);
T r_res = query(node * 2 + 1, m + 1, r, ql, qr);
return merge_val(l_res, r_res);
}
public:
// 线段树维护一个长为 n 的数组（下标从 0 到 n-1），元素初始值为 init_val
LazySegmentTree(int n, T init_val = 0) : LazySegmentTree(vector<T>(n, init_val)) {}
// 线段树维护数组 a
LazySegmentTree(const vector<T>& a) : n(a.size()), tree(2 << bit_width(a.size() - 1)) {
build(a, 1, 0, n - 1);
}
// 用 f 更新 [ql, qr] 中的每个 a[i]
// 0 <= ql <= qr <= n-1
// 时间复杂度 O(log n)
void update(int ql, int qr, F f) {
update(1, 0, n - 1, ql, qr, f);
}
// 返回用 merge_val 合并所有 a[i] 的计算结果，其中 i 在闭区间 [ql, qr] 中
// 0 <= ql <= qr <= n-1
// 时间复杂度 O(log n)
T query(int ql, int qr) {
return query(1, 0, n - 1, ql, qr);
}
};
int main() {
LazySegmentTree<long long, long long> t(8); // 默认值为 0
t.update(3, 5, 100);
t.update(4, 6, 10);
cout << t.query(0, 7) << endl;
vector<long long> nums = {3, 1, 4, 1, 5, 9, 2, 6};
LazySegmentTree<long long, long long> t2(nums);
t2.update(3, 5, 1);
t2.update(4, 6, 1);
cout << t2.query(0, 7) << endl;
return 0;
}
