题意可以理解为找到一条 $1$ 到 $n$ 的路径,使得其中 $a$ 的最大值和 $b$ 的最大值之和最小。

我们可以先按照 $a$ 的值排序,然后使用 LCT 维护关于 $b$ 的最小生成树;算法的正确性很容易证明:对于每一个 $a$ 的最大值我们都取到了 $b$ 的最大值的最小值。

维护动态最小生成树:对于新加的边 $(u, v)$ ,如果已经连接,则需要断掉其中最大的一条(当前的 $b$ 值比最大的 $b$ 值还大就不用加了),否则无脑 link 。所以我们的 LCT 还要存储下最大的边以及对应的编号。

由于 LCT 只能维护点不能维护边,我们可以考虑化边为点,总共有 $n$ 个 LCT 中的点表示实际意义的点,以及 $m$ 的 LCT 中的点表示实际意义的边。这样子瞎搞即可。

注意一定要当 $1$ 和 $n$ 已经联通时才能用当前的状态尝试更新答案哦!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// ==============================
// author: memset0
// website: https://memset0.cn
// ==============================
#include <bits/stdc++.h>
#define ll long long

int read() {
int x = 0; bool m = 0; char c = getchar();
while (!isdigit(c) && c != '-') c = getchar();
if (c == '-') m = 1, c = getchar();
while (isdigit(c)) x = x * 10 + c - '0', c = getchar();
if (m) return -x; else return x;
}

const int maxn = 50010, maxm = 100010, maxp = 150010;

int n, m, u, v, a, b, t, ans = 1e9;

int fa[maxp], ch[maxp][2], max[maxp], pto[maxp], lazy[maxp], val[maxp];

struct edge {
int u, v, a, b;
} g[maxm];

bool cmp(edge a, edge b) {
return a.a < b.a;
}

bool is_root(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
bool get_son(int x) { return ch[fa[x]][1] == x; }

void update(int x) {
max[x] = val[x], pto[x] = x;
if (ch[x][0] && max[pto[ch[x][0]]] > max[pto[x]]) pto[x] = pto[ch[x][0]];
if (ch[x][1] && max[pto[ch[x][1]]] > max[pto[x]]) pto[x] = pto[ch[x][1]];
}

void rotate(int x) {
if (!x || !fa[x]) return;
int f = fa[x], fson = get_son(x);
int ff = fa[f], ffson = get_son(f);
int y = ch[x][fson ^ 1];
if (!is_root(f)) ch[ff][ffson] = x;
fa[y] = f, fa[f] = x, fa[x] = ff;
ch[f][fson] = y, ch[x][fson ^ 1] = f;
update(f), update(x);
}

void clean_up(int x) {
if (!is_root(x)) clean_up(fa[x]);
if (lazy[x]) {
std::swap(ch[x][0], ch[x][1]);
lazy[ch[x][0]] ^= 1;
lazy[ch[x][1]] ^= 1;
lazy[x] = 0;
}
}

void splay(int x) {
clean_up(x);
while (!is_root(x)) {
int f = fa[x];
if (!is_root(f)) {
if (get_son(x) ^ get_son(f)) rotate(x);
else rotate(f);
}
rotate(x);
}
update(x);
}

void access(int x) {
for (int y = 0; x; y = x, x = fa[x])
splay(x), ch[x][1] = y, update(x);
}

void mroot(int x) {
access(x), splay(x);
lazy[x] ^= 1;
}

void select(int u, int v) {
mroot(u), access(v), splay(v);
}

int get_root(int x) {
access(x), splay(x);
while (ch[x][0]) x = ch[x][0];
return x;
}

void link(int u, int v) {
mroot(u);
fa[u] = v;
}

void cut(int u, int v) {
select(u, v);
fa[u] = ch[v][0] = 0;
update(v);
}

int main() {

n = read(), m = read();
for (int i = 1; i <= m; i++) {
g[i].u = read(), g[i].v = read();
g[i].a = read(), g[i].b = read();
}
std::sort(g + 1, g + m + 1, cmp);

for (int i = 1; i <= m; i++)
val[n + i] = g[i].b;
for (int i = 1; i <= m; i++) {
u = g[i].u, v = g[i].v;
a = g[i].a, b = g[i].b;
if (get_root(u) == get_root(v)) {
select(u, v), t = pto[v];
if (max[t] > b) {
cut(g[t - n].u, t);
cut(t, g[t - n].v);
link(u, i + n);
link(i + n, v);
}
} else {
link(u, i + n);
link(i + n, v);
}
if (get_root(1) == get_root(n)) {
select(1, n);
ans = std::min(ans, a + max[pto[n]]);
}
}

printf("%d\n", ans == 1e9 ? -1 : ans);

return 0;
}