首页 > Rinne Loves Dynamic Graph
开通博客写题解
头像 苟且的狮子
发表于 2020-07-28 20:59:56
Bellman-Ford算法，dijstra算法，循环dp问题 这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！ 题意： 分析： 首先，我不会分层图！！！！所以，这题我主要是围绕dp展开。我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数那么边权就为x,1/(x 展开全文
去ta的博客 赞 (3) 回复(1) 收起
头像 肖先生~
发表于 2020-07-23 22:56:37
分层最短路与最短路dp 方法一：分层最短路 1.首先我们对这个函数进行分析，发现他是一个周期为3的周期函数，也就是说经过三次迭代就会回到之前的数2.怎么说呢，现在就是有一种怪怪的感觉，代码什么地都能看懂，也都能敲的出来，但是感觉还是没有深刻的理解题目的意思，我去看题解都是说分三层，然后跑一遍dijk 展开全文
去ta的博客 赞 (2) 回复(1) 收起
头像 sunny_forever
发表于 2021-07-10 15:31:57
思路 求从 1 到 n 的最短路，需注意的是 图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会 执行一次操作：x = 1/(1-x)，x 是 边权，所有的 x 指所有边即 边权会随着走过的边的数目的改变而改变 所以该题 不再仅仅是最短路问题，而是变成了 最短路 + dp 问题 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 Clouder0
发表于 2020-07-21 21:48:22
Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/显然变动函数是一个周期函数，相信大家都做过类似的数学题。 设经过边数为 ，边权为 ，将 代入即可求得当时边权。随 展开全文
去ta的博客 赞 (1) 回复(1) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”