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
话说这道题被神犇xzy推荐给我写spfa入门题，然后狂TLE不止...把这道题当成入门题给我我也是醉了......
这一题其实我们只需将边按a权值排序，再一条边一条边地插入，每次跑一遍最短路即可轻松AC。(o_o)
好吧，其实spfa还是我很久以前写的了。显然裸的spfa肯定是跑不过的，于是我们需要加一点小小的优化，那就是每次不清空dis数组，改为直接将新边连接的两个点加入队列，跑一遍spfa(话说我也不知道这为什么复杂度是对的【其实是不对的】)就可以AC了。
UPD:已经在UOJ上被卡掉了
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#define maxn 100001
#define INF 2147483647 using namespace std;
typedef long long llg; struct data{
int t,f,c1,c2;
bool operator < (const data &h)const{return c1<h.c1;}
}s[maxn];
int head[maxn],to[maxn<<],next[maxn<<],l,r;
int c[maxn<<],dis[maxn],d[maxn],n,m,tt,ans;
bool w[maxn]; int getint(){
int w=,q=;
char c=getchar();
while((c<''||c>'')&&c!='-') c=getchar();
if(c=='-') q=,c=getchar();
while(c>=''&&c<='') w=w*+c-'',c=getchar();
return q?-w:w;
} void spfa(){
d[r++]=;w[]=;
while(l!=r){
int u=d[l++];l%=maxn;w[u]=;
for(int i=head[u],v;v=to[i],i;i=next[i])
if(dis[v]==- || dis[v]>max(dis[u],c[i])){
dis[v]=max(dis[u],c[i]);
if(!w[v]){
w[v]=;d[r++]=v;
r%=maxn;
}
}
}
} int main(){
n=getint();m=getint();
memset(dis,-,sizeof(dis));
for(int i=;i<=m;i++){
s[i].t=getint();s[i].f=getint();
s[i].c1=getint();s[i].c2=getint();
}
sort(s+,s+m+);ans=INF;dis[]=;
for(int i=;i<=m;i++){
int f=s[i].f,t=s[i].t;
to[++tt]=f;next[tt]=head[t];head[t]=tt;
to[++tt]=t;next[tt]=head[f];head[f]=tt;
c[tt-]=c[tt]=s[i].c2;l=r=;
if(dis[t]!=-) d[r++]=t,w[t]=;
if(dis[f]!=-) d[r++]=f,w[f]=;
spfa();
if(dis[n]!=-) ans=min(ans,dis[n]+s[i].c1);
}
if(ans==INF) printf("-1");
else printf("%d",ans);
}
下面我还是准备讲讲复杂度很对的一种做法(虽然跑的更慢)。我们仍然将边按a权值排序，然后我们只要快速求出1到n的最小生成树(或者最短路也可以)。虽然spfa可以跑过，但这个算法复杂度毕竟不对，我们还是要追求一种复杂度比较对的算法。其实，我们只要动态维护最小生成树就可以了。那么用什么呢？CDQ图分治或许可以，但我选择了LCT。其实以前我对于边带权值的动态树我一直是懵逼的，直到orz了hzwer大神的题解，我才发现了一种极其优秀的做法。我们可以把边也建成节点，而且只有边所代表的节点才有权值。这样就非常好做了是不？我们splay上维护一个区间最大值不就可以了是么？剩下的就是link-cut-tree的模板了。
我觉得这道题是一道LCT的好题。如果你还不会LCT，请前往：[Hnoi2010]Bounce 弹飞绵羊 [Sdoi2008]Cave 洞穴勘测
如果你会LCT但是就是A不了这题，推荐你还是仔细啃一啃这道题的代码吧。
这道题AC代码(LCT)如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define maxn 150010
#define maxm 100010 using namespace std;
typedef long long llg; struct data{
int u,v,a,b;
bool operator < (const data &h)const{return a<h.a;}
}ss[maxm];
int val[maxn],s[maxn][],fa[maxn],maxv[maxn],d[maxn],ans,n,m;
bool rev[maxn]; int getint(){
int w=;bool q=;
char c=getchar();
while((c>''||c<'')&&c!='-') c=getchar();
if(c=='-') q=,c=getchar();
while(c>=''&&c<='') w=w*+c-'',c=getchar();
return q?-w:w;
} bool isroot(int x){return x!=s[fa[x]][] && x!=s[fa[x]][];}
int findrt(int x){while(fa[x]) x=fa[x];return x;} void update(int x){
int l=s[x][],r=s[x][];maxv[x]=x;
if(val[maxv[l]]>val[maxv[x]]) maxv[x]=maxv[l];
if(val[maxv[r]]>val[maxv[x]]) maxv[x]=maxv[r];
} void R(int x){
int p=fa[x],g=fa[p];
bool l=(x==s[fa[x]][]),r=!l;
if(!isroot(p)) s[g][p==s[g][]]=x;
fa[s[x][l]]=p; s[p][r]=s[x][l];
fa[p]=x; s[x][l]=p; fa[x]=g;
update(p); update(x);
} void splay(int x){ //将x旋到当前splay的根节点
d[d[]=]=x;
for(int i=x;!isroot(i);i=fa[i]) d[++d[]]=fa[i];
for(int i=d[],u;u=d[i],i;i--)
if(rev[u]){
swap(s[u][],s[u][]);rev[u]=;
rev[s[u][]]^=;rev[s[u][]]^=;
}
while(!isroot(x)){
int p=fa[x],g=fa[p];
if(!isroot(p)){
if((x==s[p][])^(p==s[g][])) R(x);
else R(p);
}
R(x);
}
} void access(int u){ //将u到splay根节点的路径打通
for(int t=;u;t=u,u=fa[u])
splay(u),s[u][]=t,update(u);
} void makert(int u){ //把u换到它所在splay的根,并把沿途路径反向
access(u);
splay(u);rev[u]^=;
} int query(int u,int v){ //查询u到v的边中的最大值
makert(u);access(v);splay(v);
return maxv[v];
} void cut(int u,int v){ //把u和v的连接断掉,谁是父亲无关紧要
makert(u);access(v);splay(v);
s[v][]=fa[u]=; update(v);
} void link(int u,int v){ //把u的父亲变成v
makert(u);fa[u]=v;
} int main(){
File("a");
n=getint();m=getint();
for(int i=;i<=m;i++){
ss[i].u=getint();ss[i].v=getint();
ss[i].a=getint();ss[i].b=getint();
}
sort(ss+,ss+m+);ans=(<<);
for(int i=,u,v,t;i<=m;i++){
u=ss[i].u;v=ss[i].v;
if(findrt(u)==findrt(v)){
t=query(u,v);
if(val[t]>ss[i].b){
cut(ss[t-n].u,t);
cut(ss[t-n].v,t);
}
else continue;
}
val[i+n]=ss[i].b;maxv[i+n]=i+n;
link(u,i+n);link(v,i+n);
if(findrt()==findrt(n))
ans=min(ans,ss[i].a+val[query(,n)]);
}
printf(ans==(<<)?"-1":"%d",ans);
return ;
}