0%
【题解】P2387 [NOI2014] 魔法森林
题目大意
给出一个有$n$个节点$m$条边的无向图,节点编号为$1-n$,边编号为$1-m$。初始时小E同学在$1$号节点。数据可能包含重边和自环。
每条边都有一个妖怪住在边上。在节点$1$处有两种守护精灵A,B,每种都有无数个。无向图中每条边都有权值$a_i$和$b_i$,当且仅当小E身上携带的A守护精灵不少于$a_i$,且B守护精灵不少于$b_i$,这条边上的妖怪不会对通过这条边的人发起攻击。
求在不被妖怪袭击的情况下,到$n$号节点最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的个数与 B 型守护精灵的个数之和。
$2\le n \le 50000, 0\le m \le 100000, 1\le a_i,b_i \le 50000$