ExaWizards 2019 F
没记到，淦。
CF773D
有一个 $n$ 个点的完全图，每两个点之间有一条长度为 $w_{i,j}$ 的无向边。构造以 t 为根的生成树，使得树上每个节点到根最短边的长度和最小。
对于每个 \(t\) 求答案。
\(n \le 2000\)。
把所有边减去最小的权值，设最小的边的一端为 x，于是转化成求 x 到 t 一条链的权值。
又可以发现，一定可以构造出一种最优情况，使链上的点从与最小边相连的点到 e 是 依次递增的。
这个结论可以用反证法证明：
如果链上有一条递减的边，那么把这条边放到链的起始位置答案肯定不劣，
因为前面较大的边并不会对链上的代价作出任何贡献.
由于链上的边权依次递增，每条边都只会作出一次贡献，相当于是一条 路径.
所以我们从与最小边相连的点 s 出发跑一遍最短路就可以计算得到。
跑 dj 松弛即可。
CF843D
给定一个有向图，q 次操作
- 询问 1 到 t 的最短路
- 将一些边的边权+1
\(n,m\le 10^5, q\le 2000, \sum|s_i|\le 10^6\)