|
题目 1685 [NOI 2014]魔法森林
2014-10-16 21:46:23
|
|
|
>_<果然状态才是最重要的啊>_<
前段时间做了这么多次都没有拿到满分，今天只提交一遍就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= = |
|
我对于一个不是单峰函数的函数做3分，居然过了9个点= =多弱的数据啊
|