显然满足的条件是一个偏序关系
我们把所有边权按照a排序，按a从小到大顺序加边
然后我们发现b上的问题就是一个动态最小瓶颈生成树问题，刚好可以用动态树维护
代码暂时还没写
upd:代码写完了
第一次写的时候tmd nroot写错了。。。
#include#include using namespace std;int n, m;int ch[150010][2], fa[150010], st[150010], pos[150010], val[150010];bool lazy[150010];int u[150010], v[150010];struct edge { int x, y, a, b; } a[100010];void chkmin(int &a, int b) { if (a > b) a = b; }int ans = 0x3f3f3f3f, tot;bool nroot(int x) { return ch[fa[x]][1] == x || ch[fa[x]][0] == x; }void rev(int x) { swap(ch[x][0], ch[x][1]), lazy[x] ^= 1; }void pushup(int x){ if (val[pos[ch[x][0]]] < val[pos[ch[x][1]]]) pos[x] = pos[ch[x][1]]; else pos[x] = pos[ch[x][0]]; if (val[x] > val[pos[x]]) pos[x] = x;}void pushdown(int x){ if (lazy[x] == 1) { if (ch[x][0]) rev(ch[x][0]); if (ch[x][1]) rev(ch[x][1]); lazy[x] = 0; }}void rotate(int x){ int y = fa[x], z = fa[y]; int k = ch[y][1] == x, w = ch[x][k ^ 1]; if (nroot(y)) ch[z][ch[z][1] == y] = x; ch[x][k ^ 1] = y, ch[y][k] = w; if (w) fa[w] = y; fa[y] = x, fa[x] = z; pushup(y), pushup(x);}void splay(int x){ int y = x, top = 0; st[++top] = y; while (nroot(y)) st[++top] = y = fa[y]; while (top > 0) pushdown(st[top--]); while (nroot(x)) { int y = fa[x], z = fa[y]; if (nroot(y)) rotate((ch[y][1] == x) ^ (ch[z][1] == y) ? x : y); rotate(x); } pushup(x);}void access(int x){ for (int y = 0; x > 0; x = fa[y = x]) splay(x), ch[x][1] = y, pushup(x);}void makeroot(int x){ access(x), splay(x), rev(x);}int findroot(int x){ access(x), splay(x); while (ch[x][0]) pushdown(x), x = ch[x][0]; return x;}void split(int x, int y){ makeroot(x), access(y), splay(y);}void link(int x, int y){ makeroot(x); if (findroot(y) != x) fa[x] = y;}void cut(int x, int y){ makeroot(x); if (findroot(y) == x && fa[x] == y && ch[x][1] == 0) ch[y][0] = fa[x] = 0, pushup(y);}int main(){ scanf("%d%d", &n, &m); tot = n; for (int i = 1; i <= m; i++) scanf("%d%d%d%d", &a[i].x, &a[i].y, &a[i].a, &a[i].b); sort(a + 1, a + 1 + m, [](const edge &a, const edge &b) { return a.a < b.a; }); for (int i = 1; i <= m; i++) { makeroot(a[i].x); if (findroot(a[i].y) == a[i].x) { if (val[pos[a[i].y]] > a[i].b) { int p = pos[a[i].y]; cut(p, u[p]); cut(p, v[p]); p = ++tot; u[p] = a[i].x; v[p] = a[i].y; val[p] = a[i].b; pos[p] = p; link(p, u[p]); link(p, v[p]); } } else { int p = ++tot; u[p] = a[i].x; v[p] = a[i].y; val[p] = a[i].b; pos[p] = p; link(p, u[p]); link(p, v[p]); } makeroot(1); if (findroot(n) == 1) chkmin(ans, val[pos[n]] + a[i].a); } printf("%d\n", ans == 0x3f3f3f3f ? -1 : ans); return 0;}