Google 面经：图论问题

分享一个Google的面试经历，题目是图论相关的。

Screening Round

题目描述：

一个城镇有N个城市，一些城市之间有道路相连。每条道路需要一定的通行时间。 给定道路网络，表示为一个边的列表：

`edges = [ [u, v, h], ... ]`

其中：

• `u` 和 `v` 是城市索引。
• `h` 是 `u` 和 `v` 之间通行的所需时间（小时）。
  

同时给定：

• 一个源城市 `s`。
• 一个查询列表。 每个查询包含：
• 一个目标城市 `d`
• 一个时间
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  Unlock interview details and practice with AI
  Curated Interview Questions from Top Companies
  
• Query Processing: 对于给定的 `(destination, H)`，在累计时间列表上使用二分查找（lower bound）来找到在 `H` 小时内访问了多少个城市。
  

时间复杂度：

Dijkstra: `O(N log N + E log N)`

这个题目有一些模糊啊

怎么现在new grad都问这么难的题了，lz面的是什么岗哪个组

请问楼主，最短路径是从s 到d的时间最少的路径还是说经过的城市最少的路径？目标是求从s到d，在固定时间里，经过的城市最多多少的意思吗？不是很理解意思能解释一下吗？

如果用Dijkstra’s Algorithm计算从源城市 `s` 开始，预先计算到所有其他城市的最短路径，我们保存的是经过的城市最少的路径且时间最少的路径吧？

请问如何Preprocessing: 对于每个节点，我们怎么知道最短路径且最多城市以及在该路径上访问每个城市的时间? 似乎我们只有城市最少的路径？

有点像AIMA第三章的内容