谷歌intern OA，难到不想说话

Fan6897 · 2021-10-12 04:39:27

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

匿名用户-BKSYJ *2021-10-12 09:17:21* · 2021-10-12 09:17:21

Fan6897 发表于 2021-10-12 04:39
你大概是想多了。如果k是一个入度为0的点，你想连接(n+1)->k，那么直接连接这两个点一定是cost最小的连法 ...

哦哦！对对！你说的对！

HaruJiang · 2021-10-12 12:38:57

匿名者发表于 2021-10-8 22:50
第一题读的不是很清楚，感觉可以先loop一边公路，看看有哪些节点是没有办法访问的（只有出去的路，没有来的 ...

感觉你这个思路很靠谱

匿名用户-R3BWM *2021-10-13 14:00:40* · 2021-10-13 14:00:40

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

qubatuer · 2021-10-21 15:31:53

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

yeqinqing · 2021-10-28 02:25:03

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

BroSoap

第一题Dijkstra感觉可以做，从所有当前已经连上的node开始，把周围能连的node都加到PQ里一个一个pop，作为优化，记录当前的修路cost，大于等于直接从N+1那个点修一条路过去的话就不用进pq了