题目描述
为了得到书法大家的真传，小 E 同学下定决心去拜访住在魔法森林中的隐 士。魔法森林可以被看成一个包含 n 个节点 m 条边的无向图，节点标号为 1,2,3,…,n，边标号为 1,2,3,…,m。初始时小 E 同学在 1 号节点，隐士则住在 n 号节点。小 E 需要通过这一片魔法森林，才能够拜访到隐士。
魔法森林中居住了一些妖怪。每当有人经过一条边的时候，这条边上的妖怪 就会对其发起攻击。幸运的是，在 1 号节点住着两种守护精灵：A 型守护精灵与 B 型守护精灵。小 E 可以借助它们的力量，达到自己的目的。
只要小 E 带上足够多的守护精灵，妖怪们就不会发起攻击了。具体来说，无 向图中的每一条边 ei 包含两个权值 ai 与 bi 。若身上携带的 A 型守护精灵个数不 少于 ai ，且 B 型守护精灵个数不少于 bi ，这条边上的妖怪就不会对通过这条边 的人发起攻击。当且仅当通过这片魔法森林的过程中没有任意一条边的妖怪向 小 E 发起攻击，他才能成功找到隐士。
由于携带守护精灵是一件非常麻烦的事，小 E 想要知道，要能够成功拜访到 隐士，最少需要携带守护精灵的总个数。守护精灵的总个数为 A 型守护精灵的 个数与 B 型守护精灵的个数之和。
输入输出格式
输入格式：
输入文件的第 1 行包含两个整数 n,m，表示无向图共有 n 个节点，m 条边。 接下来 m 行，第i+ 1 行包含 4 个正整数 Xi,Yi,ai,bi，描述第i条无向边。 其中Xi与 Yi为该边两个端点的标号，ai 与 bi 的含义如题所述。 注意数据中可能包含重边与自环。
输出格式：
输出一行一个整数：如果小 E 可以成功拜访到隐士，输出小 E 最少需要携 带的守护精灵的总个数；如果无论如何小 E 都无法拜访到隐士，输出“-1”（不 含引号）。
输入输出样例
输入样例#1：
4 5
1 2 19 1
2 3 8 12
2 4 12 15
1 3 17 8
3 4 1 17
输出样例#1：
32
输入样例#2：
3 1
1 2 1 1
输出样例#2：
-1
考虑两个权值的MST？
a排序后b无序啊，LCT是可以维护动态加边的MST的啊
这里不会有连通块分开，所以判连通在用个并查集能快一点 还有一种做法，动态加边SPFA，a排序每次加入边权值为b和边的两个端点到队列。。。。。快了1倍多
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define pa t[x].fa
#define lc t[x].ch[0]
#define rc t[x].ch[1]
const int N=15e4+,M=1e5+,INF=1e9;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
} int n,m,Q,type;
struct LCTnode{
int ch[],fa,rev,w,mx,p;
}t[N];
inline int wh(int x){return t[pa].ch[]==x;}
inline int isRoot(int x){return t[pa].ch[]!=x&&t[pa].ch[]!=x;}
inline void update(int x){
t[x].p=x;t[x].mx=t[x].w;
if(t[lc].mx>t[x].mx) t[x].mx=t[lc].mx,t[x].p=t[lc].p;
if(t[rc].mx>t[x].mx) t[x].mx=t[rc].mx,t[x].p=t[rc].p;
}
inline void rever(int x){
t[x].rev^=;
swap(lc,rc);
}
inline void pushDown(int x){
if(t[x].rev){
rever(lc);
rever(rc);
t[x].rev=;
}
}
inline void rotate(int x){
int f=t[x].fa,g=t[f].fa,c=wh(x);
if(!isRoot(f)) t[g].ch[wh(f)]=x;t[x].fa=g;
t[f].ch[c]=t[x].ch[c^];t[t[f].ch[c]].fa=f;
t[x].ch[c^]=f;t[f].fa=x;
update(f);update(x);
}
int st[N],top;
inline void splay(int x){
top=;st[++top]=x;
for(int i=x;!isRoot(i);i=t[i].fa) st[++top]=t[i].fa;
for(int i=top;i>=;i--) pushDown(st[i]); for(;!isRoot(x);rotate(x))
if(!isRoot(pa)) rotate(wh(x)==wh(pa)?pa:x);
}
inline void Access(int x){
for(int y=;x;y=x,x=pa){
splay(x);
rc=y;
update(x);
}
}
inline void MakeR(int x){
Access(x);splay(x);
rever(x);
}
inline int FindR(int x){
Access(x);splay(x);
while(lc) x=lc;
return x;
}
inline void Link(int x,int y){
MakeR(x);
t[x].fa=y;
}
inline void Cut(int x,int y){
MakeR(x);Access(y);splay(y);
t[y].ch[]=t[x].fa=;
update(y);
}
inline int Que(int x,int y){
MakeR(x);Access(y);splay(y);
return t[y].p;
} struct edge{
int u,v,a,b;
bool operator <(const edge &r)const{return a<r.a;}
}e[M];
int ans=INF;
int fa[N];
inline int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void Kruskal(){
for(int i=;i<=n;i++) fa[i]=i;
sort(e+,e++m);
for(int i=;i<=m;i++){
int u=e[i].u,v=e[i].v;
if(find(u)!=find(v)){
fa[find(u)]=find(v);
Link(u,i+n),Link(v,i+n);
t[i+n].w=t[i+n].mx=e[i].b;
t[i+n].p=i+n;
}else{
int p=Que(u,v);
if(t[p].w>e[i].b){
Cut(e[p-n].u,p),Cut(e[p-n].v,p);
Link(u,i+n),Link(v,i+n);
t[i+n].w=t[i+n].mx=e[i].b;
t[i+n].p=i+n;
}
}
if(find()==find(n)) ans=min(ans,e[i].a+t[Que(,n)].w);
}
} int main(){
//freopen("in.txt","r",stdin);
n=read();m=read();
for(int i=;i<=m;i++) e[i].u=read(),e[i].v=read(),e[i].a=read(),e[i].b=read();
Kruskal();
printf("%d",ans==INF?-:ans);
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=5e4+,M=1e5+,INF=1e9;
typedef long long ll;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,m;
struct data{
int u,v,a,b;
bool operator <(const data &r)const{return a<r.a;}
}a[M];
struct edge{
int v,ne,w;
}e[M<<];
int cnt,h[N];
inline void ins(int u,int v,int w){
cnt++;
e[cnt].v=v;e[cnt].w=w;e[cnt].ne=h[u];h[u]=cnt;
cnt++;
e[cnt].v=u;e[cnt].w=w;e[cnt].ne=h[v];h[v]=cnt;
}
int d[N],q[N],head,tail,inq[N];
inline void lop(int &x){if(x==) x=N-;else if(x==N) x=;}
inline void push(int v){
if(d[v]<d[q[head]]) lop(--head),q[head]=v;
else q[tail++]=v,lop(tail);
inq[v]=;
}
void spfa(){
while(head!=tail){
int u=q[head++];inq[u]=;lop(head);
for(int i=h[u];i;i=e[i].ne){
int v=e[i].v,w=e[i].w;
if(d[v]>max(d[u],w)){
d[v]=max(d[u],w);
if(!inq[v]) push(v);
}
}
}
}
int ans=INF;
void solve(){
sort(a+,a++m);
head=tail=;
memset(d,0x3f,sizeof(d));
q[tail++]=;d[]=;inq[]=;
for(int i=;i<=m;i++){
ins(a[i].u,a[i].v,a[i].b);
head=tail=;
q[tail++]=a[i].u;inq[a[i].u]=;
q[tail++]=a[i].v;inq[a[i].v]=;
spfa();
ans=min(ans,a[i].a+d[n]);
}
}
int main(int argc, const char * argv[]) {
n=read();m=read();
for(int i=;i<=m;i++) a[i].u=read(),a[i].v=read(),a[i].a=read(),a[i].b=read();
solve();
printf("%d",ans==INF?-:ans);
}