狗一道follow up，求大神看看怎么写的

生蚝来十个 发表于 2021-6-16 14:18
感谢分享。感觉这个Stack Overflow的post应该可行。
想到另一个follow up：如果给出每个city加满油的价 ...

昨天Google的时候好像看到有人写论文讨论这个问题。。。我感觉应该挺麻烦的

三十六度五分 发表于 2021-6-17 02:08
懂了。我把问题想的太复杂了。其实我觉得我想法是对的，我想到的是构建新图，然后面试官一直question我在 ...

面试不就是这样，45分钟要是走错路了很容易拐不了弯，我一直都觉得运气和实力五开。

我觉得这道题目和蠡口伊尔就散很神似 那道题也要处理折返怎么办 首先我觉得这道题目用bfs是正确方向 而且我觉得有一点可以确认就是bfs返回的值肯定就是最短的 否则用Bfs也没有意义 所以谁能第一个到达终点最就是那个值。 其次我们在这里要防止返回的无限循环 所以油量就是时间 我们只需要一个哈利表去存储油量和结点对子， 如果这个对子出现过 说明走过 而且因为是bfs所以走过的含义就是早于现在的时间 所以我们直接忽略就可以了，如果有问题的话欢迎指正 我并不觉得这里要用到dp。

qinxnelaine 发表于 2021-6-17 05:14
我觉得这道题目和蠡口伊尔就散很神似 那道题也要处理折返怎么办 首先我觉得这道题目用bfs是正确方向 而且我 ...

你是对的。我面试的时候被面试官问糊涂了

qinxnelaine 发表于 2021-6-17 05:14
我觉得这道题目和蠡口伊尔就散很神似 那道题也要处理折返怎么办 首先我觉得这道题目用bfs是正确方向 而且我 ...

和层主差不多的思路，我觉得我们可以加一个memo 来存储 到达一个stop的当前最大油量来减枝
比如
A(10) -> B(9) -> A(8) -> .....
我默认这个图是个无向图，如果是有方向，那就不用考虑了.

看到我出的题 在这里被讨论了 简直滑稽

一般我们做 dikstra's 有 pruning tree 的步骤:

for (int child : cur.adjs) {
      if (curStep + 1 < dis[child]) {
           dis[child] = curStep + 1;
           pq.offer(child);
      }
}
如果把code改成下面的样子会不会就work了:

if (capacity == 0) continue;
for (int child : cur.adjs) {
      if (curStep + 1 < dis[child]) {
           dis[child] = curStep + 1;
      }
     pq.offer(child);
}

1 如果目前的current node已经没油了，就必须停止，不search adjacent
2 已经visit过的node已经得到了shortest distance就不需要update了
3 最关键的，哪怕没能update shorter distance，我们还是往PQ里push node，这样可以折回去加油走弯路