|
spfa无优化可过
|
|
通过这个题，我发现我一直以来的Dijkstra都写错了。。
题目 1837 [国家集训队2011]飞飞侠
2017-01-11 17:47:27
|
|
题目 1837 [国家集训队2011]飞飞侠
2016-07-06 10:15:01
|
|
本题是出题人故意用堆优化Dijkstra去卡SPFA的……
那几个挂掉的提交都来自失败的SPFA作死尝试…… 注意两点：①用vector存邻接表会RE（为何不是MLE？）②数据基本是随机生成的，也就是说步长一般会很大……所以Dijktra占便宜（把那两个点算出来就可以直接跳出），但SPFA+卡时WA了…… |