1 条题解
-
0
题目分析
- 考点:图论,bfs,贪心。
- 难度:CSP-J T4
测试点 1~3
给暴力留的分。
测试点4~8
先通过bfs求出每个点到另一个点的最短路径的长度 ,然后暴力枚举四个点 ,然后求 就可以了。
复杂度 。
测试点9~10
答案就是 ,因为在完全图中,任意两点的最短路都是 。
测试点11~15
同样求出 ,然后暴力枚举三个点 ,然后求出离 点最远的点 ,但是 可能是 或者 ,所以需要求出离 点第二远的点 ,第三远的点 ,这样就一定可以找出那个最远的点。
复杂度是 。
当然也有许多其他做法。
测试点16~20
优化上一个算法。
同样求出 和 。
我们枚举两个点 ,然后经过 的最远路径一定是 其中之一。
依次考虑这几种情况,排除掉非法的情况(经过相同的点),直接枚举就可以了。
复杂度是 。
- 1
信息
- ID
- 83
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者