Description
为了得到书法大家的真传，小E同学下定决心去拜访住在魔法森林中的隐士。魔法森林可以被看成一个包含个N节点M条边的无向图，节点标号为1..N，边标号为1..M。初始时小E同学在号节点1，隐士则住在号节点N。小E需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪就会对其发起攻击。幸运的是，在号节点住着两种守护精灵：A型守护精灵与B型守护精灵。小E可以借助它们的力量，达到自己的目的。
只要小E带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无向图中的每一条边Ei包含两个权值Ai与Bi。若身上携带的A型守护精灵个数不少于Ai，且B型守护精灵个数不少于Bi，这条边上的妖怪就不会对通过这条边的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向小E发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小E想要知道，要能够成功拜访到隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为A型守护精灵的个数与B型守护精灵的个数之和。
Input
第1行包含两个整数N,M，表示无向图共有N个节点，M条边。 接下来M行，第行包含4个正整数Xi,Yi,Ai,Bi，描述第i条无向边。其中Xi与Yi为该边两个端点的标号，Ai与Bi的含义如题所述。 注意数据中可能包含重边与自环。
Output
输出一行一个整数：如果小E可以成功拜访到隐士，输出小E最少需要携带的守护精灵的总个数；如果无论如何小E都无法拜访到隐士，输出“-1”（不含引号）。
Sample Input
【输入样例1】
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
【输入样例2】
3 1
1 2 1 1
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
【输入样例2】
3 1
1 2 1 1
Sample Output
【输出样例1】
32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
32
【样例说明1】
如果小E走路径1→2→4，需要携带19+15=34个守护精灵；
如果小E走路径1→3→4，需要携带17+17=34个守护精灵；
如果小E走路径1→2→3→4，需要携带19+17=36个守护精灵；
如果小E走路径1→3→2→4，需要携带17+15=32个守护精灵。
综上所述，小E最少需要携带32个守护精灵。
【输出样例2】
-1
【样例说明2】
小E无法从1号节点到达3号节点，故输出-1。
HINT
2<=n<=50,000
0<=m<=100,000
1<=ai ,bi<=50,000
题解
$LCT$ 维护边权信息的题...但据说动态 $SPFA$ 能水过，我这么菜，像这种 $NOI$ 的题也只能靠水才能做得了...
贪心是把边按 $a$ 排序，动态加边，边权为 $b$ 。每加一条边，从边的两端点开始跑 $SPFA$ ， $SPFA$ 维护路径上的瓶颈。然后取最后加的边的 $a$ 值 + $SPFA$ 过程中维护的起点到终点的最小化瓶颈值 $b$ 的和的最小值。
注意的是动态 $SPFA$ 和 [HNOI 2014]道路堵塞 是一样的，不要去清空 $dist$ 数组。
//It is made by Awson on 2018.1.10
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define lowbit(x) ((x)&(-(x)))
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
using namespace std;
const int N = ;
const int M = ;
const int INF = ~0u>>;
void read(int &x) {
char ch; bool flag = ;
for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());
for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());
x *= -*flag;
}
void write(int x) {
if (x > ) write(x/);
putchar(x%+);
} int n, m, ans = INF;
struct ss {
int u, v, a, b;
bool operator < (const ss &tmp) const {
return a < tmp.a;
}
}e[M+];
struct tt {int to, next, cost; }edge[(M<<)+];
int path[N+], top;
int q[N+], head, tail, vis[N+], dist[N+];
void add(int u, int v, int c) {edge[++top].to = v, edge[top].next = path[u], edge[top].cost = c, path[u] = top; }
int SPFA(int u, int v) {
vis[q[head = tail = ] = u] = , ++tail, vis[q[tail] = v] = , ++tail;
while (head != tail) {
int u = q[head]; ++head, head %= N, vis[u] = ;
for (int i = path[u]; i; i = edge[i].next) {
int v = edge[i].to;
if (dist[v] > Max(dist[u], edge[i].cost)) {
dist[v] = Max(dist[u], edge[i].cost);
if (!vis[v]) vis[q[tail] = v] = , ++tail, tail %= N;
}
}
}
return dist[n];
}
void work() {
read(n), read(m);
for (int i = ; i <= m; i++) read(e[i].u), read(e[i].v), read(e[i].a), read(e[i].b);
sort(e+, e++m); for (int i = ; i <= n; i++) dist[i] = INF;
for (int i = ; i <= m; i++) {
add(e[i].u, e[i].v, e[i].b), add(e[i].v, e[i].u, e[i].b);
int tmp = SPFA(e[i].u, e[i].v); if (tmp != INF) ans = Min(ans, tmp+e[i].a);
}
if (ans != INF) write(ans);
else putchar('-'), putchar('');
}
int main() {
work();
return ;
}
动态SPFA
我已经这么菜了，肯定不能再怠惰...留个坑，用 $lct$ 再写一遍...
upd 18.1.11：填坑，码完 $lct$ 了。
对于边权问题的处理，用 $lct$ 不好简易地将边权转移为点权。解决这类问题的方法就是再开一倍点，将边变为点，表示边的点权就是原边权，而表示点的点权赋为 $0$ 。
对于这道题，方法和上面的一样，按照 $a$ 排序， $lct$ 维护最小瓶颈路。
//It is made by Awson on 2018.1.11
#include <set>
#include <map>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))
using namespace std;
const int N = ;
const int INF = ~0u>>; int n, m, w[N+], a[N+], b[N+], ans = INF;
struct tt {
int u, v, a, b;
bool operator < (const tt &tmp) const {
return a < tmp.a;
}
}e[N+];
struct Link_Cut_Tree {
Link_Cut_Tree() {for (int i = ; i <= N; i++) isrt[i] = ; }
int pre[N+], ch[N+][], rev[N+], maxi[N+], isrt[N+], pos;
void pushup(int o) {
if (!o) return;
maxi[o] = o;
if (w[maxi[ch[o][]]] > w[maxi[o]]) maxi[o] = maxi[ch[o][]];
if (w[maxi[ch[o][]]] > w[maxi[o]]) maxi[o] = maxi[ch[o][]];
}
void pushdown(int o) {
if (!rev[o] || !o) return;
int ls = ch[o][], rs = ch[o][];
Swap(ch[ls][], ch[ls][]), Swap(ch[rs][], ch[rs][]);
rev[ls] ^= , rev[rs] ^= , rev[o] = ;
}
void push(int o) {if (!isrt[o]) push(pre[o]); pushdown(o); }
void rotate(int o, int kind) {
int p = pre[o];
ch[p][!kind] = ch[o][kind], pre[ch[o][kind]] = p;
if (isrt[p]) isrt[o] = , isrt[p] = ;
else ch[pre[p]][ch[pre[p]][] == p] = o;
pre[o] = pre[p];
ch[o][kind] = p, pre[p] = o;
pushup(p), pushup(o);
}
void splay(int o) {
push(o);
while (!isrt[o]) {
if (isrt[pre[o]]) rotate(o, ch[pre[o]][] == o);
else {
int p = pre[o], kind = ch[pre[p]][] == p;
if (ch[p][kind] == o) rotate(o, !kind), rotate(o, kind);
else rotate(p, kind), rotate(o, kind);
}
}
}
void access(int o) {
int y = ;
while (o) {
splay(o);
isrt[ch[o][]] = , isrt[ch[o][] = y] = ;
pushup(o); o = pre[y = o];
}
}
void makeroot(int o) {access(o), splay(o); rev[o] ^= , Swap(ch[o][], ch[o][]); }
int find(int o) {access(o), splay(o); while (ch[o][]) o = ch[o][]; return o; }
void link(int x, int y) {makeroot(x); pre[x] = y; }
void cut(int x, int y) {makeroot(x); access(y), splay(y); ch[y][] = pre[x] = , isrt[x] = ; pushup(y); }
int query(int x, int y) {
if (find(x)^find(y)) return INF;
makeroot(x), access(y), splay(y);
return maxi[y];
}
void update(int x, int y, int c) {
int last = query(x, y);
if (last == INF) {w[++pos] = c, a[pos] = x, b[pos] = y; link(x, pos), link(y, pos); return; }
if (w[last] <= c) return;
cut(last, a[last]), cut(last, b[last]);
w[last] = c, a[last] = x, b[last] = y; link(x, last), link(y, last);
}
}T;
void work() {
scanf("%d%d", &n, &m); T.pos = n;
for (int i = ; i <= m; i++) scanf("%d%d%d%d", &e[i].u, &e[i].v, &e[i].a, &e[i].b);
sort(e+, e++m);
for (int i = ; i <= m; i++) {
T.update(e[i].u, e[i].v, e[i].b);
int tmp = T.query(, n); if (tmp != INF) ans = Min(ans, e[i].a+w[tmp]);
}
if (ans == INF) ans = -; printf("%d\n", ans);
}
int main() {
work();
return ;
}
link-cut-tree