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

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。

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掉再加入就好了

 

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #define N (500000+100)  6 using namespace std;  7 struct node  8 {  9     int a,b,x,y; 10 }line[N*2]; 11 int Father[N],Son[N][2]; 12 int Max[N],Val[N],Rev[N]; 13 int n,m,sz; 14 bool cmp(node a,node b){
   return a.a
         
          Val[Max[Son[x][0]]] && Val[x]>Val[Max[Son[x][1]]]) 21         Max[x]=x; 22     else 23         Max[x]=Val[Max[Son[x][0]]]>Val[Max[Son[x][1]]]?Max[Son[x][0]]:Max[Son[x][1]]; 24 } 25  26 void Rotate(int x) 27 { 28     int wh=Get(x); 29     int fa=Father[x],fafa=Father[fa]; 30     if (!Is_root(fa)) Son[fafa][Son[fafa][1]==fa]=x; 31     Father[fa]=x; Son[fa][wh]=Son[x][wh^1]; 32     Father[x]=fafa; Son[x][wh^1]=fa; 33     if (Son[fa][wh]) Father[Son[fa][wh]]=fa; 34     Update(fa);Update(x); 35 } 36  37 void Pushdown(int x) 38 { 39     if (Rev[x] && x) 40     { 41         if (Son[x][0]) Rev[Son[x][0]]^=1; 42         if (Son[x][1]) Rev[Son[x][1]]^=1; 43         swap(Son[x][0],Son[x][1]); 44         Rev[x]=0; 45     } 46 } 47  48 void Push(int x) 49 { 50     if (!Is_root(x)) Push(Father[x]); 51     Pushdown(x); 52 } 53  54 void Splay(int x) 55 {  56     Push(x); 57     for (int fa;!Is_root(x);Rotate(x)) 58         if (!Is_root(fa=Father[x])) 59             Rotate(Get(fa)==Get(x)?fa:x); 60 } 61  62 void Access(int x) {
   for (int y=0;x;y=x,x=Father[x]) Splay(x),Son[x][1]=y,Update(x);} 63 int Find_root(int x) {Access(x); Splay(x); while (Son[x][0]) x=Son[x][0]; return x;} 64 void Make_root(int x) {Access(x); Splay(x); Rev[x]^=1;} 65 void Link(int x,int y) {Make_root(x); Father[x]=y;} 66 void Cut(int x,int y) {Make_root(x); Access(y); Splay(y); Son[y][0]=Father[x]=0;}  67  68 void Add_line(int num,int x,int y,int l) 69 { 70     if (Find_root(x)!=Find_root(y)) 71     { 72         Link(x,num);Link(num,y); 73         Val[num]=l; 74         return; 75     } 76     Make_root(x); 77     Access(y); Splay(y); 78     if (Val[Max[y]]
         
        
       
      
     

 

SPFA：

smg啊……一开始的想法是二分a和b……

后来又口胡了一种算法只有15分……

最后发现我还是too young too simple

第一次听说到SPFA动态加边（点）这种操作orz

----------------以下题解-------------------

因为边权有两个，求起来是十分麻烦的

而正解好像要写LCT，然而我并不会

（别问我为什么知道的，因为这道题我翻的题解比你不知道多到哪里去了orz）

所以那我们就把边a排序，然后将边按a从小到大加入，再按b为权值跑SPFA

每次加一条边的时候，将边两边的端点入队再SPFA。

而且因为边是按a从小到大加入的，所以后面dis情况会包含前面的情况，dis数组就不用每次memset每次重新求了

 

#include
     
      #include
      
       #include
       
         #include
        
         #include
         
          using namespace std;struct node1{    int to,next,a,b;}edge[200020];struct node2{    int a,b,num;}node;struct node3{    int u,v,l1,l2;}line[100001];int head[50001],num_edge,dis[50001];int n,m,maxn,ans=10000000;bool used[50001];queue 
          
           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!=0;i=edge[i].next) if (max(edge[i].b,dis[x])