首页 > Rinne Loves Dynamic Graph

苟且的狮子

发表于 2020-07-28 20:59:56

Bellman-Ford算法，dijstra算法，循环dp问题这题很好，让我重新认识到了最短路到底是为解决了一个什么样的问题！！！！题意：分析：首先，我不会分层图！！！！所以，这题我主要是围绕dp展开。我们必须要知道题中所给函数1/(1-x)是个周期为三的周期函数那么边权就为x,1/(x 展开全文

sunny_forever

发表于 2021-07-10 15:31:57

思路求从 1 到 n 的最短路，需注意的是图上所有边的边权会实时改变如何改变：每次走过一条边之后，所有的 x 都会执行一次操作：x = 1/(1-x)，x 是边权，所有的 x 指所有边即边权会随着走过的边的数目的改变而改变所以该题不再仅仅是最短路问题，而是变成了最短路 + dp 问题展开全文

Clouder0

发表于 2020-07-21 21:48:22

Before the Beginning 转载请将本段放在文章开头显眼处，如有二次创作请标明。原文链接：https://www.codein.icu/nowcoderweekly16/显然变动函数是一个周期函数，相信大家都做过类似的数学题。设经过边数为，边权为，将代入即可求得当时边权。随展开全文

查看本题

查看本题讨论

等你来战

查看全部

相关比赛