2022年ccpc绵阳站E题 E. Hammer to Fall（ 倒序dp + 分块优化）

题目传送门

题目大意

在一张（带边权）图G(V, E)上，第i个点居住着ai个人。在连续q天，每天会在一个图中的某个点降落锤子。我们可以通过图中的道路运输居民，运输1个居民通过某条道路的代价为该道路的长度。
要求用最小的代价，确保q天中不会有居民被锤子砸到。

解题思路

对于该问题，首先考虑单位居民的代价，我们可以计算出单位居民代价之后 再进行整体统计。
很自然地可以发现一个可以递推地东西，某一结点地代价等于周围最小地代价，可以定义dp为某一节点地代价
d p [ u ] = m i n v ∈ ( u , v ) {   d p [ v ] + d i s ( u , v ) } dp[u]=min_{v\in(u,v)}\{ \ dp[v]+dis(u,v)\} dp[u]=minv∈(u,v)​{  dp[v]+dis(u,v)}
很自然地发现我们可以沿着时间线倒序dp，于是便有了第一版的代码
code

#include
using namespace std;
const int maxn=1e5+5;
#define ll long long 
const ll mod=998244353;
vector<pair<int,ll>>e[maxn];
int main()
<
1
2
3
4
5
6
7