* 题目大意
给定了一个 nnn 个定点 mmm 条边的无向图,找出满足条件的四个景点
输出四个景点的分数和最大值
* 思路1:
按照题目说法,两个点的距离不超过k+1,且四个点不同
可以先跑多源最短路,然后枚举四个景区,找出符合条件中的分数和的最大值
时间复杂度:O(n4)O(n^4)O(n4)
* 解法1
bfs/floyd求多远最短路+暴力枚举四个景点:时间复杂度---> O(n4)O(n^4)O(n4)-ACGO:0分,洛谷:55分
只有BFS
FLOYD+BFS
* 思路2
在解法1的基础上,考虑景点a,d,这两个点世比较特殊的,a和d一定是家的邻点
并且a和d和家的距离 ≤\leq≤ k+1的,所以我们可以优先处理最优候选点a,d
后续我们只需要枚举b和d之后再去最优候选点中查找a和d即可
* 解法2
bfs求多源最短路+枚举优化------>时间复杂度:O(n2)O(n^2)O(n2)-100pts
0PTS代码
错误点原因:因为100pts的解法是邻接表,很多人会把暴力代码(解法1)的遍历方法复制过来导致错误
正确代码(100PTS)
看在作者这么努力的份上,给个赞吧求求了……