狗。昂赛。

请问楼主，第二题去掉一个墙的意思是，问去掉哪个墙，使得在这个墙去掉之后，从source到target的最短路径是在所有可能的被去掉的墙中最小，是这个意思吗？如果是这样，那应该怎么做啊，总不能把所有的墙都尝试一遍做BFS吧？

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

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

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

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

细雨微张 发表于 2019-10-11 05:13
楼主，谢谢回复！我不确定我是不是完全理解了你的意思，我把我的理解描述如下，你看对吗？

1. 从sourc ...

不需要额外第二步啊，第一步的时候直接给wall标上距离就行。。。

瓜瓜瓜瓜瓜瓜 发表于 2019-10-10 14:52
第一题最优解nlogn，插入之前可以建立index tree使得每次插入查找位置成为logn

。。。insert的复杂度 不管你怎么知道位置，avg都是O（n）的

tuwei 发表于 2019/10/11 09:06:58
。。。insert的复杂度 不管你怎么知道位置，avg都是O（n）的

那你去学学indexed tree吧