怎么能，如此之坑。。

鄙视树状数组.......

王尼玛，看错范围了

这是Wrong了多少次才过
只是因为改过代码没保存啊！！！

0+=lowbit(0),额。。。。。。。。然后就没有然后了

= =Orz…………注意细节。。。。

>_<果然状态才是最重要的啊>_<
前段时间做了这么多次都没有拿到满分，今天只提交一遍就AC了2333333……
好吧其实这题的思路很简单= =就是从小到大枚举cur，对于每个cur把所有a权值等于cur的边加入邻接表，同时把边的两个端点加入队列中，做一次spfa(注意dis[]的转移应把加法改为max函数），当dis[n]有更新的时候，可以证明这条最短路径上所有边中a权值最大的就是cur，然后更新答案ans = min(ans, cur + dis[n])即可。。。这个做法只用了1秒多……（我在考虑要不要把时限修改一下。。。。）
不过当时这道题的出题人给出的正解是按a从小到大添边，用LCT维护一棵最小生成树，当1与n联通时更新答案……可是我太弱了不会写LCT= =

O(n^2)的算法都能过。。。。。
当然我用的O(n)

……我……恨……细……节……题……（好吧其实是我太弱）
（下附我的励志故事。。。。13号那几个TLE的代码都是作死用的Pollard_Rho= =）

哦呵呵呵呵呵.....根节点遍历+链表果断A掉，速度还好快！！！~\(≧▽≦)/~啦啦啦，今天吃了小苹果，感觉自己萌萌哒…………

这个BFS非常朴素~

回复 @默燃·凰燭·燭���陰 :
不得不orz楼上（今天第二次了吧悲剧的说），表示PK中用树写的跪了。。

mark

mark

mark

mark

一开始过了 开了o2就超时了 关了就过了

回复 @HouJikan :
x，y两遍还是会有问题的- -可以卡掉
例如这个数据：
8 4
0 0
10 1
8 10000
9 10001
1000 3
1001 4
10000 2
10001 7
显然最优解释是1,2一组，3,4一组，5，6一组，7,8一组
最优解为：17
而你的代码显然不能处理- -事实上也是这样，你跑出来是10000+ - -