JOIG 2021/2022 F 题解

链接

题意：给定一张 \(n\) 个点，\(m\) 条边的无向图（保证没有重边、自环）。边有两种，\(type=1\) 时，经过后手中的数 \(-1\)；\(type=2\) 时，经过后手中的数 \(\div2\) 下取整。给定 \(q\) 个询问以及常数 \(L\)，初始在点 \(1\) 上，每一次给定目标点 \(p\)，需要你求出最小的初始数，使得存在一种方案，使得到达 \(p\) 时该数 \(\ge1\)。

做法：\(q\) 次 Dijkstra 显然不可取。考虑计算贡献。