题目大意：给定一个 N 个点，M 条边的无向图，边有两个边权 a, b，求从 1 号节点到 N 号节点路径的两个权值和的最大值最小是多少。
题解：
对于有两个属性的结构的最优化问题，可以考虑先按照其中一个分量进行排序。接着从小到大枚举这个有序的分量，计算以当前枚举到的值为这一分量的最大值时，全局的最优解是多少。因此，需要高效维护的是如何求出另一个分量的最优解。
对于这道题来说，考虑对 a 分量进行排序，并按从小到大的顺序依次加边。对于即将加入的第 i 条边来说，若加入这条边使得两个本来不联通的点联通，则直接加入；若加入这条边之后，形成了环，则比较加入这条边 b 的权值和这条边两个端点之间路径上 b 的最大值，若当前边的 b 更小，则断开路径上最大边权的边，并加入当前这条边即可。利用 lct 进行维护 b 即可。
代码如下
#include <bits/stdc++.h>
using namespace std;
struct edge {
int x, y, a, b;
edge(int _x = 0, int _y = 0, int _a = 0, int _b = 0) {
x = _x, y = _y;
a = _a, b = _b;
}
};
struct node {
node* l;
node* r;
node* p;
int rev, b, maxb, id;
node(int _b = 0, int _id = -1) {
l = r = p = NULL;
b = _b;
id = _id;
rev = 0;
}
void unsafe_reverse() {
swap(l, r);
rev ^= 1;
}
void pull() {
maxb = b;
if (l != NULL) {
l->p = this;
maxb = max(maxb, l->maxb);
}
if (r != NULL) {
r->p = this;
maxb = max(maxb, r->maxb);
}
}
void push() {
if (rev) {
if (l != NULL) {
l->unsafe_reverse();
}
if (r != NULL) {
r->unsafe_reverse();
}
rev = 0;
}
}
};
bool is_root(node* v) {
if (v == NULL) {
return false;
}
return (v->p == NULL) || (v->p->l != v && v->p->r != v);
}
void rotate(node* v) {
node* u = v->p;
assert(u != NULL);
v->p = u->p;
if (v->p != NULL) {
if (v->p->l == u) {
v->p->l = v;
}
if (v->p->r == u) {
v->p->r = v;
}
}
if (v == u->l) {
u->l = v->r;
v->r = u;
}
if (v == u->r) {
u->r = v->l;
v->l = u;
}
u->pull();
v->pull();
}
void deal_with_push(node* v) {
static stack<node*> s;
while (true) {
s.push(v);
if (is_root(v)) {
break;
}
v = v->p;
}
while (!s.empty()) {
s.top()->push();
s.pop();
}
}
void splay(node* v) {
deal_with_push(v);
while (!is_root(v)) {
node* u = v->p;
if (!is_root(u)) {
if ((v == u->l) ^ (u == u->p->l)) {
rotate(v);
} else {
rotate(u);
}
}
rotate(v);
}
}
void access(node* v) {
node* u = NULL;
while (v != NULL) {
splay(v);
v->r = u;
v->pull();
u = v;
v = v->p;
}
}
void make_root(node* v) {
access(v);
splay(v);
v->unsafe_reverse();
}
node* find_root(node* v) {
access(v);
splay(v);
while (v->l != NULL) {
v->push();
v = v->l;
}
splay(v);
return v;
}
void link(node* v, node* u) {
if (find_root(v) != find_root(u)) {
make_root(v);
v->p = u;
}
}
void cut(node* v, node* u) {
make_root(v);
if (find_root(u) == v && u->p == v && u->l == NULL) {
u->p = v->r = NULL;
v->pull();
}
}
void split(node* v, node* u) {
make_root(v);
access(u);
splay(u);
}
node* find(node* v, int b) {
while (true) {
if (v->b == b) {
break;
}
if (v->l != NULL && v->l->maxb == b) {
v = v->l;
} else {
v = v->r;
}
}
return v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, m; // 0-indexed
cin >> n >> m;
vector<edge> e;
for (int i = 0; i < m; i++) {
int x, y, a, b;
cin >> x >> y >> a >> b;
e.emplace_back(--x, --y, a, b);
}
sort(e.begin(), e.end(), [&](const edge &x, const edge &y) {
return x.a < y.a;
});
vector<node*> t(n + m);
for (int i = 0; i < n; i++) {
t[i] = new node(0, i);
}
int ans = 1e9;
for (int i = 0; i < m; i++) {
int a = e[i].a, b = e[i].b;
int x = e[i].x, y = e[i].y;
if (find_root(t[x]) != find_root(t[y])) {
t[i + n] = new node(b, i + n);
link(t[x], t[i + n]);
link(t[y], t[i + n]);
} else {
split(t[x], t[y]);
if (b < t[y]->maxb) {
node* v = find(t[y], t[y]->maxb);
int id = v->id - n;
int vx = e[id].x, vy = e[id].y;
cut(t[vx], v), cut(t[vy], v);
t[i + n] = new node(b, i + n);
link(t[x], t[i + n]);
link(t[y], t[i + n]);
}
}
if (find_root(t[0]) == find_root(t[n - 1])) {
split(t[0], t[n - 1]);
ans = min(ans, a + t[n - 1]->maxb);
}
}
if (ans == 1e9) {
cout << "-1" << endl;
} else {
cout << ans << endl;
}
return 0;
}