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
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
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
lct：
这个基本算是lct裸题
但也学到了一点套路
如果要维护边权的话就将边看做一个点然后连接相应的两个点
至于这个点的编号？和输入的编号对应起来就好了，方便我们查找这个点对应的边的信息
这个题只需要每次将a相同的边的b权值加入树中，当前的答案就是a[i]+min(1~n路径上的最大值)
若连边连出环了怎么办？先将点x和y中最长的边cut掉再加入就好了
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (500000+100)
using namespace std;
struct node
{
int a,b,x,y;
}line[N*];
int Father[N],Son[N][];
int Max[N],Val[N],Rev[N];
int n,m,sz;
bool cmp(node a,node b){return a.a<b.a;} int Get(int x) {return Son[Father[x]][]==x;}
int Is_root(int x) {return Son[Father[x]][]!=x && Son[Father[x]][]!=x;}
void Update(int x)
{
if (Val[x]>Val[Max[Son[x][]]] && Val[x]>Val[Max[Son[x][]]])
Max[x]=x;
else
Max[x]=Val[Max[Son[x][]]]>Val[Max[Son[x][]]]?Max[Son[x][]]:Max[Son[x][]];
} void Rotate(int x)
{
int wh=Get(x);
int fa=Father[x],fafa=Father[fa];
if (!Is_root(fa)) Son[fafa][Son[fafa][]==fa]=x;
Father[fa]=x; Son[fa][wh]=Son[x][wh^];
Father[x]=fafa; Son[x][wh^]=fa;
if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
Update(fa);Update(x);
} void Pushdown(int x)
{
if (Rev[x] && x)
{
if (Son[x][]) Rev[Son[x][]]^=;
if (Son[x][]) Rev[Son[x][]]^=;
swap(Son[x][],Son[x][]);
Rev[x]=;
}
} void Push(int x)
{
if (!Is_root(x)) Push(Father[x]);
Pushdown(x);
} void Splay(int x)
{
Push(x);
for (int fa;!Is_root(x);Rotate(x))
if (!Is_root(fa=Father[x]))
Rotate(Get(fa)==Get(x)?fa:x);
} void Access(int x) {for (int y=;x;y=x,x=Father[x]) Splay(x),Son[x][]=y,Update(x);}
int Find_root(int x) {Access(x); Splay(x); while (Son[x][]) x=Son[x][]; return x;}
void Make_root(int x) {Access(x); Splay(x); Rev[x]^=;}
void Link(int x,int y) {Make_root(x); Father[x]=y;}
void Cut(int x,int y) {Make_root(x); Access(y); Splay(y); Son[y][]=Father[x]=;} void Add_line(int num,int x,int y,int l)
{
if (Find_root(x)!=Find_root(y))
{
Link(x,num);Link(num,y);
Val[num]=l;
return;
}
Make_root(x);
Access(y); Splay(y);
if (Val[Max[y]]<l) return;
int t=Max[y]-n;
Cut(line[t].x,t+n);Cut(line[t].y,t+n);
Link(x,num);Link(num,y);
Val[num]=l;
} int main()
{
int ans=0x7fffffff;
scanf("%d%d",&n,&m);
for (int i=;i<=m;++i)
scanf("%d%d%d%d",&line[i].x,&line[i].y,&line[i].a,&line[i].b);
sort(line+,line+m+,cmp);
int s=;
while (s<=m)
{
while (line[s].a==line[s+].a)
Add_line(s+n,line[s].x,line[s].y,line[s].b),s++;
Add_line(s+n,line[s].x,line[s].y,line[s].b);
s++;
if (Find_root() !=Find_root(n)) continue;
Make_root(n);
Access(); Splay();
ans=min(ans,line[s-].a+Val[Max[]]);
}
printf("%d",ans==0x7fffffff?-:ans);
}
SPFA：
smg啊……一开始的想法是二分a和b……
后来又口胡了一种算法只有15分……
最后发现我还是too young too simple
第一次听说到SPFA动态加边（点）这种操作orz
----------------以下题解-------------------
因为边权有两个，求起来是十分麻烦的
而正解好像要写LCT，然而我并不会
（别问我为什么知道的，因为这道题我翻的题解比你不知道多到哪里去了orz）
所以那我们就把边a排序，然后将边按a从小到大加入，再按b为权值跑SPFA
每次加一条边的时候，将边两边的端点入队再SPFA。
而且因为边是按a从小到大加入的，所以后面dis情况会包含前面的情况，dis数组就不用每次memset每次重新求了
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std; struct node1
{
int to,next,a,b;
}edge[]; struct node2
{
int a,b,num;
}node; struct node3
{
int u,v,l1,l2;
}line[]; int head[],num_edge,dis[];
int n,m,maxn,ans=;
bool used[];
queue <int>q; void add(int u,int v,int l1,int l2)//加边
{
++num_edge;
edge[num_edge].to=v;
edge[num_edge].next=head[u];
edge[num_edge].a=l1;
edge[num_edge].b=l2;
head[u]=num_edge;
} void spfa(int re,int fun)//动态加点，将新边的两个端点re和fun入队
{
used[re]=true;
used[fun]=true;
q.push(re);
q.push(fun);
while (!q.empty())
{
int x=q.front();
q.pop();
for (int i=head[x];i!=;i=edge[i].next)
if (max(edge[i].b,dis[x])<dis[edge[i].to])
{
dis[edge[i].to]=max(edge[i].b,dis[x]);
if (!used[edge[i].to])
{
used[edge[i].to]=true;
q.push(edge[i].to);
}
}
used[x]=false;
} } bool cmp(node3 a,node3 b)//按a权值排序
{
return a.l1<b.l1;
} int main()
{
int i;
scanf("%d%d",&n,&m);
for (i=;i<=m;++i)
scanf("%d%d%d%d",&line[i].u,&line[i].v,&line[i].l1,&line[i].l2);
sort(line+,line+m+,cmp); memset(dis,0x3f,sizeof(dis));
dis[]=;
q.push();
used[]=true;
for (i=;i<=m;++i)//按a从小到大加边
{
add(line[i].u,line[i].v,line[i].l1,line[i].l2);
add(line[i].v,line[i].u,line[i].l1,line[i].l2);
spfa(line[i].u,line[i].v);
ans=min(ans,dis[n]+line[i].l1);
}
if (ans==)
printf("-1");
else
printf("%d",ans);
}