acgo题库
  • 首页
  • 题库
  • 学习
  • 天梯
  • 备赛

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
  • 竞赛
  • 讨论
  • 团队
登录
注册
题目详情提交记录(0)
  • 详细题解?

    * 题目大意 给定了一个 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) 看在作者这么努力的份上,给个赞吧求求了……

    userId_undefined

    AC是最好的

    秩序白银
    31阅读
    0回复
    3点赞
  • 正经题解

    userId_undefined

    复仇者_零

    永恒钻石快乐小狗出题人
    75阅读
    2回复
    2点赞
暂无数据

提交答案之后,这里将显示提交结果~

首页