2022杭电多校（五）

2022杭电多校（五）

一、比赛小结

比赛链接：Problems (hdu.edu.cn)

二、题目分析及解法（基础题） 1003、Slipper

题目链接：Problem - 7187 (hdu.edu.cn)

题意：

给出一棵树，每个边的权均为 ω \omega ω ，魔法可以使得，层数差 k k k 的节点边权为 p p p

题解：

很简单的分层图题，常规思路是 每层多一个点+双向边 或 每层多两个点+单向边。

设树的深度为 d d d ，在第 i i i 层 ( 1 ≤ i ≤ d ) (1\le i \le d) (1≤i≤d) 和第 i + 1 i+1 i+1 层中新增两个点 l i , r i , l i l_i, r_i, l_i li​,ri​,li​ ， 连向所有第 i + 1 i+1 i+1 层的点， r i r_i ri​ 连向所有第 i i i 层的点，对于原来树中所有的点，向 l d e p u + k − 1 l_{dep_u+k-1} ldepu​+k−1​ 连一条权为 p p p 单向边，向 r d e p u − k r_{dep_u-k} rdepu​−k​ 连一条权值为 p p p 的单向边，在修改后的图中跑 dijkstra 求 s s s 到 t t t 的最短路即可，复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 。

代码：

#include 
#include 
#include 
#include 
using namespace std;
using ll = long long;

const int maxn = 1e6 + 5;
int e[maxn