最短路三题 POJ2139 POJ3259 POJ3268
继续按照顺序刷本应该早刷了的水.
2.5他们其实都是”图”
POJ2139
六度关系问题. 奶牛之间的路径加一块比较一下. 本来想用Dijkstra因为运行速度比较快, 后来想想Warshall_Floyd都没用过几回, 用一回熟悉一下. 结果也不慢, 数据弱.
中途发生了点小问题是没注意点从1开始到n结束, 数组还是用的0到n-1, 没有同步. 还好没花什么时间在这个问题上.
而且我发现<<挑战>> 上面列出的POJ题目不少是Discuss很少的, 不明觉厉.
POJ3259
虫洞问题. 以前做过, 不做了.
大概是用Bellman-Ford判回路的一个题. 唯一亮点在于添加一个超级源点解决出发点不确定的问题.
POJ3268
这和2139基本是一道题, 只有最后一步不一样. 非常快敲完编译没语法错误直接运行粘测例过了感觉这回要从头到尾无调试一遍AC了
结果交上去TLE了.
看来老是不算数据量就做题真是坏习惯, 1000^3 = 1e9 勉强超时, 改Dijkstra.
改了之后终于592ms 过了, 不过中途想到一种更快的方法, 必须试一试.
这种方法就是把n遍dijkstra变成2遍. s为源点算一遍, 然后把所有的边都反过来再算一遍, 加起来就好.
有两种实现方法
- 改数据结构, 把所有的边都放进邻接表(就像对待无向图那样), 用tag来标记他们的方向, 然后根据tag进行两遍Dijkstra
- 多建一个表, 把反过来的边插进另一个表, 两遍Dijkstra.
考虑了一下打算用方法2, 因为可以省脑子.
AC后发现是79ms, 哈哈哈