标签: 最短路

3 篇文章

义乌中学暑假集训 2021.07.14 D
给定一个 $n$​ 个节点,$m$ 条边无向图,初始边权均为 $1$。有 $k$ 次操作,每次操作可以选取一条边,使其边权加一。 设一条边的边权为 $v$​​,定义经过该边的时间为 $\frac{1}{v}$​​。 现有两个人,其中一个从 $s_1$ 走到 $t_1$,一个从 $s_2$ 走到 $t_2$,问如何操作使得两人花费总时间最少? $n,…
Luogu P5060 旅行 题解
Describe 题目链接 给定一个 $N$ 个点, $M$ 条边的有向图,求从 $A$ 到 $B$ 的路径上边权和是 $P$ 的倍数的最短路径的长度及路径。 对于所有数据,$2\leq N \leq$$ 5\times $${10}^{4}$$,M\leq$$ 2 \times {10}^5$$ , 1\leq P $$\leq 50$。 Sol…