ACM习题集

ZZULIOJ_链式前向星_BFS_hipercijevi

心累,手动再见

这道题如果在链式前向星没有学的前提下,一定会觉得储存方式很玄学。。。

这道题主要就是卡 vector 的时间,我用 vector 的各种方法都试了,就是过不了, 学长用 vector 神奇的 过了 。不可思议。。。。vector 由于本身的问题,在保存大数据时,效率不高。

关于超时,简直有点玄学,明明感觉复杂度不高的,不知道是 vector 的锅,还是循环的锅。恶心的是 OJ 上不能看到自己超了多长时间。关于 vector 的优化方法可以参考这几篇文章

关于链式前向星,其精华就在于用一个简单的线性表,将复杂的逻辑结构保存了下来。想到这个方法的人绝对是个大牛。刚开始分析的时候,我盯着数据看了几个小时 (╯‵□′)╯︵┻━┻

只能说大牛们都太牛了,我还是记住结论好了。。  然而实际上。。。在 啊哈算法 这本书里,的邻接表存储 也引入的 next 和 head 数组 ,要是之看的仔细的话,其实这次是可以更快的理解这个数据结构的。

一篇关于链式前向星的文章 链式前向星介绍

AC 解

用 bfs 遍历链式前向星,这里的输入外挂,还有待研究,但对效果来说,直接将时间减少了 0.3 秒,还是相当可观的。神奇。。。

 

发表评论

电子邮件地址不会被公开。