对于这一题, 我们考虑直接求出路径是非常麻烦的.
那么采用一个枚举答案的办法, 因为取值范围有限, 我们直接枚举边即可.
我们枚举(A)的取值, 直接维护另一边的(B).
考虑钦定的这条边一定要被选. 那么小于这条边的权值的边只要保证(1), (N)两者联通就可以了.
于是我们对另一边维护一个最小生成树.
这个可以把边单独建成LCT中的点, 然后点的权为0, 边的权为边权. 然后直接维护即可.
其实这题就是一个套路题, 在有两种元素的情况下(比如这题/坐标), 我们可以枚举1维度, 用东西去维护另一个维度, 这样一定能遍历出所有解.
Code
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for(int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
typedef long long LL;
typedef long double LD;
int read() {
char ch = getchar();
int x = 0, flag = 1;
for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
return x * flag;
}
void write(int x) {
if (x < 0) putchar('-'), x = -x;
if (x >= 10) write(x / 10);
putchar(x % 10 + 48);
}
const int Maxn = 50009, Maxm = 100009, Maxv = 50009;
struct edge {
int u, v, a, b;
bool operator < (const edge &Another) const {
return a < Another.a;
}
};
template <int N> struct LCT {
struct node {
int fa, ch[2], revTag;
pair<int, int> sumVal; int val;
}t[N];
int amt, _top, stk[N];
#define fa(x) t[(x)].fa
#define lc(x) t[(x)].ch[0]
#define rc(x) t[(x)].ch[1]
int isroot(int u) { return t[t[u].fa].ch[0] != u && t[t[u].fa].ch[1] != u; }
void pushup(int u) {
t[u].sumVal = max(make_pair(t[u].val, u), max(t[lc(u)].sumVal, t[rc(u)].sumVal));
}
void setRev(int u) {
t[u].revTag ^= 1;
swap(lc(u), rc(u));
}
void pushdown(int u) {
if (t[u].revTag) {
t[u].revTag = 0;
setRev(lc(u)), setRev(rc(u));
}
}
void rotate(int u) {
int y = fa(u), z = fa(y), dir = (rc(y) == u);
if (!isroot(y)) t[z].ch[rc(z) == y] = u; t[u].fa = z;
t[y].ch[dir] = t[u].ch[dir ^ 1]; t[t[u].ch[dir ^ 1]].fa = y;
t[u].ch[dir ^ 1] = y; t[y].fa = u;
pushup(y), pushup(u);
}
void splay(int u) {
stk[_top = 1] = u;
for (int jwb = u; !isroot(jwb); jwb = t[jwb].fa) stk[++_top] = t[jwb].fa;
while (_top) pushdown(stk[_top--]);
while (!isroot(u)) {
int y = t[u].fa, z = t[y].fa;
if (!isroot(y))
(t[z].ch[1] == y) ^ (t[y].ch[1] == u) ? rotate(u) : rotate(y);
rotate(u);
}
pushup(u);
}
void access(int u) {
for (int y = 0; u; u = fa(y = u))
splay(u), t[u].ch[1] = y, pushup(u);
}
void makeRoot(int u) {
access(u), splay(u), setRev(u);
}
int findRoot(int u) {
access(u); splay(u);
while (lc(u)) pushdown(u), u = lc(u);
return u;
}
void link(int u, int v) { makeRoot(u); splay(u); t[u].fa = v; }
void cut(int u, int v) {
makeRoot(u); access(v); splay(v);
if (findRoot(v) == u && t[u].fa == v && t[v].ch[0] == u) {
t[u].fa = t[v].ch[0] = 0;
pushup(v);
}
}
pair<int, int> split(int u, int v) {
makeRoot(u); access(v); splay(v);
return t[v].sumVal;
}
int newnode(int val, int pa = 0) {
int res = ++amt;
t[res].val = val;
t[res].sumVal = make_pair(val, res);
t[res].fa = pa;
return res;
}
#undef fa
#undef lc
#undef rc
};
template <int N> struct DSU {
int fa[N];
void init() { rep (i, 0, N - 1) fa[i] = i; }
int find(int u) { return u ^ fa[u] ? fa[u] = find(fa[u]) : u; }
bool connected(int u, int v) { return find(u) == find(v); }
void merge(int u, int v) {
u = find(u), v = find(v);
if (u != v) fa[u] = v;
}
};
static edge g[Maxm];
static int n, m;
static int ans = INT_MAX, cntNode;
static int virtualId[Maxn + Maxm];
pair <int, int> lst[Maxm + Maxn];
DSU <Maxn + Maxm> ufs;
LCT <Maxn + Maxm> tur;
void init() {
n = read(), m = read();
rep (i, 1, m) {
int u = read(), v = read(), a = read(), b = read();
g[i] = (edge){u, v, a, b};
}
ufs.init();
rep (i, 1, n) virtualId[i] = tur.newnode(0);
/**/cntNode = n;
}
inline bool Connected(int u, int v) { return ufs.connected(u, v); }
inline void Link(int u, int v, int val) {
virtualId[++cntNode] = tur.newnode(val);
tur.link(virtualId[u], virtualId[cntNode]);
tur.link(virtualId[v], virtualId[cntNode]);
lst[cntNode] = make_pair(u, v);
ufs.merge(u, v);
}
inline int Query(int u, int v) { return tur.split(virtualId[u], virtualId[v]).first; }
inline void Cut(int u, int v) {
int res = tur.split(u, v).second;
tur.cut(lst[res].first, res); tur.cut(lst[res].second, res);
}
void solve() {
sort(g + 1, g + m + 1);
rep (i, 1, m) {
bool addFlag = false;
int u = g[i].u, v = g[i].v, a = g[i].a, b = g[i].b;
if (Connected(u, v) == false) {
addFlag = true;
Link(u, v, b);
} else
if (b < Query(u, v)) Cut(u, v), Link(u, v, b), addFlag = true;
if (addFlag && Connected(1, n) == true) ans = min(ans, a + Query(1, n));
}
cout << (ans == INT_MAX ? -1 : ans) << endl;
}
int main() {
// freopen("LG2387.in", "r", stdin);
// freopen("LG2387.out", "w", stdout);
init();
solve();
#ifdef Qrsikno
debug("
Running time: %.3lf(s)
", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
return 0;
}