bzoj3669

对于这道题的解法，感觉是部分暴力，枚举带几只A型守护精灵，就可以将这道题转化成求类似于bzoj2594了。

参考题解：

http://wenku.baidu.com/view/a611cec4dd3383c4bb4cd2d8.html

http://www.cnblogs.com/JoeFan/p/4451249.html

找错时深刻体会到老师讲的静态测试能找出一半的错。

（昨天把手机电池摔坏了，借别人的手机定闹钟，结果因为重新开了下机，手机时间12点左右，正常时间11点左右，所以造成定的6点多的闹钟，抬头看外面黑暗暗的，就决定继续睡，还想着，今天太累了，实在起不来，结果后来发现真相的我眼泪掉下来）

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define N 50010
#define M 100010
#define INF 0x3f3f3f3fstruct node{node *fa;node *ch[2];int rev;int val;int valnum;int maxval;int maxvalnum;int from;int to;void init(int tempval,int tempvalnum,int tempfrom,int tempto){ch[0]=ch[1]=fa=NULL;rev=0;val=tempval;valnum=tempvalnum;maxval=val;maxvalnum=valnum;from=tempfrom;to=tempto;}bool isroot(){return fa==NULL||(fa->ch[0]!=this&&fa->ch[1]!=this);}void fswitch(){rev^=1;swap(ch[0],ch[1]);return;}void push_down(){if(rev){if(ch[0]){ch[0]->fswitch();}if(ch[1]){ch[1]->fswitch();}rev=0;}return;}void go(){if(!isroot()){fa->go();}push_down();return;}int dir(){return fa->ch[1]==this?1:0;}void setedge(int d,node *another){ch[d]=another;if(another){another->fa=this;}return;}void push_up(){maxval=val;maxvalnum=valnum;if(ch[0]){if(maxvalnum<ch[0]->maxvalnum){maxvalnum=ch[0]->maxvalnum;maxval=ch[0]->maxval;}}if(ch[1]){if(maxvalnum<ch[1]->maxvalnum){maxvalnum=ch[1]->maxvalnum;maxval=ch[1]->maxval;}}return;}void rot(){int d=dir();node *tempfafa=fa->fa;if(!(fa->isroot())){tempfafa->ch[fa->dir()]=this;}fa->setedge(d,ch[!d]);setedge(!d,fa);fa=tempfafa;ch[!d]->push_up();return;}void splay(){go();while(!isroot()){if(!(fa->isroot())){dir()==fa->dir()?fa->rot():rot();}rot();}push_up();return;}void access(){for(node *p=this,*q=NULL;p;q=p,p=p->fa){p->splay();p->setedge(1,q);p->push_up();}splay();return;}void make_root(){access();fswitch();return;}void cut(node *another){another->make_root();access();ch[0]->fa=NULL;ch[0]=NULL;push_up();return;}void link(node *another){another->make_root();another->fa=this;return;}node *find_root(){node *temp=this;while(temp->fa){temp=temp->fa;}return temp;}bool islink(node *another){return find_root()==another->find_root()?true:false;}int querymax(node *another){another->make_root();access();return maxval;}
};struct edge{int from,to;int ai,bi;
};bool cmp(edge a,edge b){return a.ai<b.ai;
}node *tree[2*N],pool[2*N];
edge edgearray[M];
int cou;void addedge(int x,int y,int w){if(x==y){return;}else{if(tree[x]->islink(tree[y])){int temp=tree[x]->querymax(tree[y]);if(tree[temp]->valnum>w){//把w写成了x，wr了，强调：想着意义写代码，每个代码都是一段故事（文艺版）tree[temp]->cut(tree[tree[temp]->from]);tree[temp]->cut(tree[tree[temp]->to]);tree[temp]->init(temp,w,x,y);tree[temp]->link(tree[y]);tree[temp]->link(tree[x]);}}else{tree[++cou]=&(pool[cou]);tree[cou]->init(cou,w,x,y);tree[cou]->link(tree[x]);tree[cou]->link(tree[y]);}return;}
}int main(){int n,m;scanf("%d%d",&n,&m);if(m==0){//printf("wo shi da hao ren");printf("-1\n");}else{for(int i=1;i<=n;i++){tree[i]=&(pool[i]);tree[i]->init(i,-1,-1,-1);}cou=n;for(int i=0;i<m;i++){scanf("%d%d%d%d",&edgearray[i].from,&edgearray[i].to,&edgearray[i].ai,&edgearray[i].bi);}sort(edgearray,edgearray+m,cmp);int ans=INF;int nowai=edgearray[0].ai;for(int i=0;i<m;i++){if(edgearray[i].ai!=nowai){if(tree[1]->islink(tree[n])){int temp=tree[1]->querymax(tree[n]);if(nowai+tree[temp]->valnum<ans){ans=nowai+tree[temp]->valnum;}}nowai=edgearray[i].ai;}addedge(edgearray[i].from,edgearray[i].to,edgearray[i].bi);}if(tree[1]->islink(tree[n])){int temp=tree[1]->querymax(tree[n]);if(edgearray[m-1].ai+tree[temp]->valnum<ans){ans=edgearray[m-1].ai+tree[temp]->valnum;}}if(ans==INF){printf("-1\n");}else{printf("%d\n",ans);}}return 0;
}