为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为 1…n1…n，边标号为1…m1…m。初始时小E同学在 11 号节点，隐士则住在 nn 号节点。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在 11 号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边 eiei 包含两个权值 aiai 与 bibi。若身上携带的A型守护精灵个数不少于 aiai，且B型守护精灵个数不少于 bibi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
输入格式
第1行包含两个整数 n,mn,m，表示无向图共有 nn 个节点，mm 条边。
接下来 mm 行，第 i+1i+1 行包含4个正整数 xi,yi,ai,bixi,yi,ai,bi，描述第 ii 条无向边。其中 xixi 与 yiyi 为该边两个端点的标号，aiai 与 bibi的含义如题所述。
注意数据中可能包含重边与自环。
输出格式
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1-1”（不含引号）。
样例一
input
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
output
32 按a从小到大加边，发现出现环时，删掉这个环上的b最大值，lct维护
（然而spfa可过……
#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;
int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
struct na{
int x,y,a,b,ne;
bool v;
}b[];
int n,m,x,y,a,c,ma=,u[],dis[],ans,num=,l[];
queue <int> q;
const int INF=1e9;
inline void in(int x,int y,int a,int c){b[++num].x=x;b[num].y=y;b[num].a=a;b[num].b=c;b[num].ne=l[x];l[x]=num;}
inline bool cmp(int x,int y){return b[x].a<b[y].a;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
bool v[];
inline void pu(int x){
if (!v[x]) v[x]=,q.push(x);
}
inline void gx(){
while (!q.empty()){
x=q.front();q.pop();v[x]=;
for (y=l[x];y;y=b[y].ne)
if (b[y].v&&dis[b[y].y]>dis[x]&&dis[b[y].y]>b[y].b) dis[b[y].y]=max(dis[x],b[y].b),pu(b[y].y);
}
}
int main(){
register int i,j=;
n=read();m=read();
for (i=;i<=m;i++) x=read(),y=read(),a=read(),c=read(),ma=max(a,ma),in(x,y,a,c),in(y,x,a,c);
for (i=;i<=num;i++) u[i]=i;
sort(u+,u++num,cmp);
for (i=;i<=n;i++) dis[i]=INF;
ans=INF;
for (i=;i<=ma;i++){
if (b[u[j]].a==i) for (;b[u[j]].a==i;j++) b[u[j]].v=,pu(b[u[j]].x),pu(b[u[j]].y);
gx();
ans=min(ans,dis[n]+i);
}
if (ans==INF) ans=-;printf("%d\n",ans);
}
spfa
#include<cstdio>
#include<algorithm>
#define MN 50001
#define MM 200001
using namespace std;
int read_p,read_ca;
inline int read(){
read_p=;read_ca=getchar();
while(read_ca<''||read_ca>'') read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p;
}
struct na{
int x,y,a,b,ne;
bool v;
}b[MM];
int n,m,x,mma=,ans,l[MN],ch[MN][],fa[MN],st[MN],ma[MN],lo[MN];
const int INF=1e9;
inline bool cmp(na x,na y){return x.a<y.a;}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
bool rev[MN];
inline bool isroot(int x){
return ch[fa[x]][]!=x&&ch[fa[x]][]!=x;
}
inline void pd(int x){
if (rev[x]) swap(ch[x][],ch[x][]),rev[ch[x][]]^=,rev[ch[x][]]^=,rev[x]=;
}
inline void up(int x){ pd(x);pd(ch[x][]);pd(ch[x][]); if (b[ma[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=ma[ch[x][]]; if (b[ma[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b&&b[ma[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=ma[ch[x][]]; if (b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=lo[ch[x][]]; if (b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[ma[ch[x][]]].b&&b[lo[ch[x][]]].b>=b[lo[ch[x][]]].b) ma[x]=lo[ch[x][]]; }
inline void rot(int x){
int y=fa[x],kind=ch[y][]==x,t=lo[x];
if(!isroot(y)) ch[fa[y]][ch[fa[y]][]==y]=x;
lo[x]=lo[y];
if (ch[x][!kind]) lo[y]=lo[ch[x][!kind]],lo[ch[x][!kind]]=t;else lo[y]=t;
fa[x]=fa[y];fa[y]=x;
ch[y][kind]=ch[x][!kind];
ch[x][!kind]=y;
fa[ch[y][kind]]=y;
up(y);
}
inline void splay(int x){
int i=x,to=;
while (!isroot(i)) st[++to]=i,i=fa[i];up(i);
for (;to;to--) up(st[to]);
while (!isroot(x)){
if (isroot(fa[x])) rot(x);else
if ((ch[fa[x]][]==x)==(ch[fa[fa[x]]][]==fa[x])) rot(fa[x]),rot(x);else rot(x),rot(x);
}
up(x);
}
inline void acc(int x){for (int u=;x;x=fa[u=x]) splay(x),ch[x][]=u;}
inline void re(int x){acc(x);splay(x);rev[x]^=;}
inline void in(int k){
int x=b[k].x,y=b[k].y;
acc(x);re(y);
fa[y]=x;ch[x][]=y;lo[y]=k;
}
inline void del(int k){
int x=b[k].x,y=b[k].y;
re(x);acc(y);splay(x);
ch[x][]=fa[y]=lo[y]=;
}
inline int find(int x){acc(x);splay(x);while (ch[x][]) x=ch[x][];return x;}
inline bool qu(int x,int y){
return find(x)==find(y);
}
inline int que(){
if (!qu(,n)) return INF;
re();acc(n);splay(n);return b[ma[n]].b;
}
inline int qam(int x,int y){
re(x);acc(y);splay(y);
return ma[y];
}
int main(){
register int i,j=;
n=read();m=read();
for (i=;i<=m;i++) b[i].x=read(),b[i].y=read(),b[i].a=read(),b[i].b=read(),mma=max(b[i].a,mma);
sort(b+,b++m,cmp);
ans=INF;
for (i=;i<=mma;i++){
for (;b[j].a==i;j++){
if (!qu(b[j].x,b[j].y)) in(j);else{
x=qam(b[j].x,b[j].y);if (b[x].b>b[j].b) del(x),in(j);
}
}
ans=min(ans,que()+i);
}
if (ans==INF) ans=-;printf("%d\n",ans);
}
lct