[LeetCode]Reachable Nodes In Subdivided Graph

我们直接把输入看成带权图即可，这道题本质上就是最短路径，但是区别是，如果我们发现M步之内无法从当前点去往下一个点，我们仍然会取当前边的一部分。比如从u到v需要10步，我们只剩下6不可以走，我们仍然会取这六个点。这里有一个情况需要注意一下，就是同一条边，如果我们只能取部分，可能会取到两次。比如u到v存在一条无向边，长度为10，我们到u的时候还剩8步，我们取了8个点。然后我们从其他某个点到达v，还剩5步，如果我们取了5个点这里就有重复了，长度为10的边我们却取了13个点，这是明显不行的。这里我们需要做一些特殊的处理，假设我们现在在顶点u，剩下的步数不够到达顶点v，连接u和v的边的长度为w，我们还剩下k步：

• 如果v是还没有visited过的点，我们取边上k个点即可。得到source到v的最短路径shortestPath[v]
• 如果v是已经被visited过的点，有可能出现上面提到的重复的情况。我们需要查看visit v的时候已经取了多少个节点，这个我们可以通过shortestPath[v]推出，等于总步数M - shortestPath[v]。根据这个值来决定取k还是w - (M - shortestPath[v])即可。

时间复杂度就是Dijkstra的复杂度O(E * log V)，空间复杂度O(V + E)，代码如下：