新鲜详细的狗家跪经， 有一道题请大家指教

楼主能不能说说第一题的解题思路？谢谢！

简单的dijstra算法

_Perry 发表于 2021-2-15 17:10
我来说一个O(m*n*log(m*n))的解法：

从终点向起点反推。维护一个最小堆，堆的元素是(cost, position)。c ...

你这个思路基本应该是Bellman–Ford。 感觉这题Bellman–Ford比Dijsktra要好。

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

bigboss789 发表于 2021-2-18 12:09
你这个思路基本应该是Bellman–Ford。 感觉这题Bellman–Ford比Dijsktra要好。

没看懂，大佬求个详情。

第四题用 dijkstra 类似一六三姨

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

bigboss789 发表于 2021-3-12 11:35
不是大佬。。。 你可以比较下Bellman–Ford和Dijsktra。

我个人的理解就是Dijsktra在pop出一个vertex ...

第一轮我也不懂 但是我看过出现很多次 在线蹲大佬。

lyronly 发表于 2021-2-13 17:26
明白了。感觉是蠡口 level 7 的题。
每个元素的值只能变大不能变小。
引入一个维度 dp[x][y][v]  为 {0 ...

请问我为什么感觉V越大cost越大？需要计大于V的cost最小值吗

_Perry 发表于 2021-2-15 17:10
我来说一个O(m*n*log(m*n))的解法：

从终点向起点反推。维护一个最小堆，堆的元素是(cost, position)。c ...

额外代价似乎需要知道从终点到当前的max