题意：有一张无向图，每条边有两个权值。求选取一些边使1和n连通，且max(a[i])+max(b[i])最小
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
思路：LCT模板
将a[i]排序，维护路径上b[i]的最大值
因为是无向图且连通情况不变，不用findroot检查是否连通，并查集即可
也许是OI生涯最后一次打LCT
1 var t:array[0..300000,0..1]of longint; 2 rev,fa,mx,w,a,b,f,q,x,y:array[0..300000]of longint; 3 n,m,i,j,u,v,ans,tmp,top:longint; 4 5 procedure swap(var x,y:longint); 6 var t:longint; 7 begin 8 t:=x; x:=y; y:=t; 9 end; 10 11 function min(x,y:longint):longint; 12 begin 13 if x<y then exit(x); 14 exit(y); 15 end; 16 17 function isroot(x:longint):boolean; 18 begin 19 if (t[fa[x],0]<>x)and(t[fa[x],1]<>x) then exit(true); 20 exit(false); 21 end; 22 23 procedure pushup(p:longint); 24 var l,r:longint; 25 begin 26 l:=t[p,0]; r:=t[p,1]; 27 mx[p]:=p; 28 if w[mx[l]]>w[mx[p]] then mx[p]:=mx[l]; 29 if w[mx[r]]>w[mx[p]] then mx[p]:=mx[r]; 30 end; 31 32 procedure pushdown(p:longint); 33 var l,r:longint; 34 begin 35 l:=t[p,0]; r:=t[p,1]; 36 if rev[p]=1 then 37 begin 38 rev[p]:=0; rev[l]:=rev[l] xor 1; rev[r]:=rev[r] xor 1; 39 swap(t[p,0],t[p,1]); 40 end; 41 end; 42 43 procedure rotate(x:longint); 44 var y,z,l,r:longint; 45 begin 46 y:=fa[x]; z:=fa[y]; 47 if t[y,0]=x then l:=0 48 else l:=1; 49 r:=l xor 1; 50 if not isroot(y) then 51 begin 52 if t[z,0]=y then t[z,0]:=x 53 else t[z,1]:=x; 54 end; 55 fa[x]:=z; fa[y]:=x; fa[t[x,r]]:=y; 56 t[y,l]:=t[x,r]; t[x,r]:=y; 57 pushup(y); 58 pushup(x); 59 end; 60 61 procedure splay(x:longint); 62 var y,z,k:longint; 63 begin 64 inc(top); q[top]:=x; 65 k:=x; 66 while not isroot(k) do 67 begin 68 inc(top); q[top]:=fa[k]; 69 k:=fa[k]; 70 end; 71 while top>0 do 72 begin 73 pushdown(q[top]); 74 dec(top); 75 end; 76 77 while not isroot(x) do 78 begin 79 y:=fa[x]; z:=fa[y]; 80 if not isroot(y) then 81 begin 82 if (t[y,0]=x)xor(t[z,0]=y) then rotate(x) 83 else rotate(y); 84 end; 85 rotate(x); 86 end; 87 end; 88 89 procedure access(x:longint); 90 var k:longint; 91 begin 92 k:=0; 93 while x>0 do 94 begin 95 splay(x); t[x,1]:=k; pushup(x); 96 k:=x; x:=fa[x]; 97 end; 98 end; 99 100 procedure makeroot(x:longint); 101 begin 102 access(x); splay(x); rev[x]:=rev[x] xor 1; 103 end; 104 105 procedure link(x,y:longint); 106 begin 107 makeroot(x); fa[x]:=y; 108 end; 109 110 procedure split(x,y:longint); 111 begin 112 makeroot(x); access(y); splay(y); 113 end; 114 115 procedure cut(x,y:longint); 116 begin 117 makeroot(x); access(y); splay(y); t[y,0]:=0; fa[x]:=0; 118 pushup(y); 119 end; 120 121 function query(x,y:longint):longint; 122 begin 123 split(x,y); 124 exit(mx[y]); 125 end; 126 127 procedure qsort(l,r:longint); 128 var i,j,mid:longint; 129 begin 130 i:=l; j:=r; mid:=a[(l+r)>>1]; 131 repeat 132 while mid>a[i] do inc(i); 133 while mid<a[j] do dec(j); 134 if i<=j then 135 begin 136 swap(a[i],a[j]); 137 swap(b[i],b[j]); 138 swap(x[i],x[j]); 139 swap(y[i],y[j]); 140 inc(i); dec(j); 141 end; 142 until i>j; 143 if l<j then qsort(l,j); 144 if i<r then qsort(i,r); 145 end; 146 147 function find(k:longint):longint; 148 begin 149 if f[k]<>k then f[k]:=find(f[k]); 150 exit(f[k]); 151 end; 152 153 begin 154 assign(input,'bzoj3669.in'); reset(input); 155 assign(output,'bzoj3669.out'); rewrite(output); 156 readln(n,m); 157 for i:=1 to n do f[i]:=i; 158 for i:=1 to m do read(x[i],y[i],a[i],b[i]); 159 qsort(1,m); 160 ans:=maxlongint; 161 162 for i:=1 to m do 163 begin 164 u:=x[i]; v:=y[i]; 165 if find(u)=find(v) then 166 begin 167 tmp:=query(u,v); 168 if w[tmp]>b[i] then 169 begin 170 cut(tmp,x[tmp-n]); 171 cut(tmp,y[tmp-n]); 172 end 173 else 174 begin 175 if find(1)=find(n) then 176 begin 177 tmp:=query(1,n); 178 ans:=min(ans,w[tmp]+a[i]); 179 end; 180 continue; 181 end; 182 end 183 else f[find(u)]:=find(v); 184 w[i+n]:=b[i]; mx[i+n]:=i+n; 185 link(u,i+n); link(v,i+n); 186 if find(1)=find(n) then 187 begin 188 tmp:=query(1,n); 189 ans:=min(ans,w[tmp]+a[i]); 190 end; 191 end; 192 if ans=maxlongint then writeln(-1) 193 else writeln(ans); 194 close(input); 195 close(output); 196 end.