题解：P11046 [蓝桥杯 2024 省 Java B] 星际旅行

· · 题解

简化题意

给定 n 个点，m 条双向边，求从 x_i 点出发最多经过 y_i 条边，所能到达的点的个数。

思路

我们用一个二维数据 d_{i,j} 表示从第 i 个点走到第 j 个点最少要经过几条边，可以跑一遍迪杰斯特拉来求出来。然后对于第 k 个盲盒，从 1 枚举到 n 算出有几个点 i 满足 d_{x_k,i}\leq y_k 。

代码