【BZOJ】3669: [Noi2014]魔法森林（lct）

#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << (#x) << " = " << (x) << endl
#define error(x) (!(x)?puts("error"):0)
#define rdm(x, i) for(int i=ihead[x]; i; i=e[i].next)
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<‘0‘||c>‘9‘; c=getchar()) if(c==‘-‘) k=-1; for(; c>=‘0‘&&c<=‘9‘; c=getchar()) r=r*10+c-‘0‘; return k*r; }

const int oo=~0u>>1, N=50005, M=100005;
int w[M];
struct node *null;
struct node {
	node *f, *c[2];
	int pos, k, rev;
	node(int _p=0) { pos=k=_p; f=c[0]=c[1]=null; }
	void setc(node *x, bool d) { c[d]=x; x->f=this; }
	bool d() { return f->c[1]==this; }
	bool check() { return f==null || (f->c[0]!=this && f->c[1]!=this); }
	void upd() { if(this==null) return; rev=!rev; swap(c[0], c[1]); }
	void pushup() { pos=k; if(w[c[0]->pos]>w[pos]) pos=c[0]->pos; if(w[c[1]->pos]>w[pos]) pos=c[1]->pos; }
	void pushdown() { if(rev) rev=0, c[0]->upd(), c[1]->upd(); }
};
void rot(node *x) {
	node *f=x->f;
	f->pushdown(); x->pushdown(); bool d=x->d();
	if(f->check()) x->f=f->f;
	else f->f->setc(x, f->d());
	f->setc(x->c[!d], d);
	x->setc(f, !d);
	f->pushup();
}
void fix(node *x) { if(!x->check()) fix(x->f); x->pushdown(); }
void splay(node *x) {
	fix(x);
	while(!x->check())
		if(x->f->check()) rot(x);
		else x->d()==x->f->d()?(rot(x->f), rot(x)):(rot(x), rot(x));
	x->pushup();
}
node *access(node *x) {
	node *y=null;
	for(; x!=null; y=x, x=x->f) splay(x), x->c[1]=y;
	return y;
}
void mkroot(node *x) { access(x)->upd(); splay(x); }
void split(node *x, node *y) { mkroot(x); access(y); splay(y); }
void link(node *x, node *y) { mkroot(x); x->f=y; }
void cut(node *x, node *y) { split(x, y); y->c[0]->f=null; y->c[0]=null; }
node *findrt(node *x) { access(x); splay(x); while(x->c[0]!=null) x=x->c[0]; return x; }
int ask(node *x, node *y) { split(x, y); return y->pos; }

struct dat { int u, v, a, b; }e[M];
node *root[N+M];
int n, m, ans=oo;

bool cmp(const dat &a, const dat &b) { return a.a<b.a; }
void init() {
	w[0]=-oo;
	sort(e+1, e+1+m, cmp);
	for1(i, 1, m) w[i]=e[i].b;

	null=new node; null->f=null->c[0]=null->c[1]=null;
	for1(i, 1, n) root[i]=new node;
	for1(i, 1, m) root[i+n]=new node(i);

	for1(i, 1, m) {
		int u=e[i].u, v=e[i].v;
		if(findrt(root[u])==findrt(root[v])) {
			int pos=ask(root[u], root[v]);
			if(w[pos]>e[i].b) {
				cut(root[u], root[pos+n]);
				cut(root[v], root[pos+n]);
				link(root[u], root[i+n]);
				link(root[v], root[i+n]);
			}
		}
		else { link(root[u], root[i+n]); link(root[v], root[i+n]); }
		if(findrt(root[1])==findrt(root[n])) ans=min(ans, e[i].a+w[ask(root[1], root[n])]);
	}
}

int main() {
	read(n); read(m);
	for1(i, 1, m) read(e[i].u), read(e[i].v), read(e[i].a), read(e[i].b);
	init();
	printf("%d\n", ans==oo?-1:ans);
	return 0;
}