weride sde ng oa

匿名用户 发表于 2022-8-16 19:31
第二道题算每个node到ABC的距离，最后遍历所有的node求每个node到ABC的和

牛的呀，思路绝了

这应该是OA1，刚做完

ginowan 发表于 2022-8-27 14:54
这应该是OA1，刚做完

请问可以问下第二题的思路吗

匿名用户 发表于 2022-8-16 16:31
第二道题算每个node到ABC的距离，最后遍历所有的node求每个node到ABC的和

请问这种方法可以避免重复加已经走过的edge的weight吗

EddyHonkMan 发表于 2022-8-20 17:55
感觉很对！

请问这种方法可以避免重复加已经走过的edge的weight吗

tsintings 发表于 2022-8-27 09:27
牛的呀，思路绝了

请问这种方法可以避免重复加已经走过的edge的weight吗

匿名用户 发表于 2022-8-27 16:09
请问这种方法可以避免重复加已经走过的edge的weight吗

能的 你可以自己构建一个你觉得会走重复路的例子 然后你会发现 它根本不会算上重复的那部分

哦哦确实，所以就是对所有点计算从这个点开始的bfs，然后找一个点到ABC三个点距离和最短的点对吧，不过好像是得用dijkstra而不是bfs？

EddyHonkMan 发表于 2022-8-20 20:55
感觉很对！

大佬，请问你看懂第二题是啥意思了吗？就是求A到C的最短路径吗？可不可以用DFS？

匿名用户 发表于 2022-8-27 20:07
哦哦确实，所以就是对所有点计算从这个点开始的bfs，然后找一个点到ABC三个点距离和最短的点对吧，不过好像 ...

请问这个第二题不是问A到B到C的距离最短路径吗，为什么要计算所有的点分别到ABC的距离呢？