夜间模式暗黑模式
字体
阴影
滤镜
圆角
主题色
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$。

Solution

设$dis[i][j]$表示从起点出发走到$i$的路径边权和$\% P=j$的最小值。
那么跑一次$Dijikstra$即可。
注意转移$dis[to][v+w[i]]=dis[u][v]+w[i]$。
保存路径可以记录根节点最后递归输出。
由于此题出题人不是特别友好,所以此题卡$spfa$,本人亲测$spfa$只有$80pts$。

关于spfa,她死了

Code

暂无评论

发送评论 编辑评论


				
上一篇
下一篇