微软笔试题目提问

微软的笔试:有n个小镇,有m条路将n个小镇连接起来,n个小镇中,有k个小镇设置有医院,问其他小镇到最近的医院要多久?
我当时直接以每个医院作为源点,做了k次dijkstra,有没有时间复杂度更小的算法啊?总感觉会超时,忘记数据范围是多少了。菜鸡提问,求各位大佬康康~
#微软实习##微软##笔试题目#
全部评论
可以找一个虚拟点,然后让这个虚拟点到所有医院连边,这些边的距离都是0,然后用这个虚拟点跑一边dijkstra应该就可以了
9 回复 分享
发布于 2022-03-05 20:02
leetcode腐烂的橘子 多源最短路
点赞 回复 分享
发布于 2023-05-05 12:03 北京
同学,你有收到面试邀约了嘛
点赞 回复 分享
发布于 2022-03-12 16:59

相关推荐

评论
点赞
13
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务