bzoj1576的帮我们跑好最短路版本23333（双倍经验！嘿嘿嘿

　　这题可以用树链剖分或并查集写。树链剖分非常显然，并查集的写法比较妙，涨了个姿势，原来并查集的路径压缩还能这么用...

　　首先对于不在最短路径树上的边x->y，设t为最短路径树上lca(x,y)，则t到y上的路径上的点i到根的距离都可以用h[x]+dis[x][y]+h[y]-h[i]（h[]为深度）来更新，因为h[i]一定，只要让h[x]+dis[x][y]+h[y]最小就行，这里用树剖直接修改整条链上的数，就可以过了。

　　并查集的方法就很巧妙了...把不在最短路径树上的边找出来，按照h[x]+dis[x][y]+h[y]从小到大排序。然后按排序后的边的顺序更新答案，被更新过了的必然不会被再次更新。更新的方法就是每次两个指针从x和y一步步向t靠近并更新沿途上没更新过的点，同时用并查集记录这些更改过的点的顶部，下次更新下面跑到这里的点直接就可以跳到没修改的地方。好像感觉其实就是把树剖改成用并查集来跳跳跳而已...

　　只写了并查集，树剖的下次补（QAQ模板都不会打了已经

　　UPD 2017.6.28：今天复习了下树剖，然后把这题写了嘿嘿嘿。这题最后只查询叶子结点，所以就不用上传了，非常好写。

树链剖分：

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long long using namespace std;const int maxn=500010,inf=1000000000;struct poi{
    int too,pre,sum;}e[maxn];struct tjm{
    int sum,tag;}a[maxn];struct zs{
    int x,y,len;}edge[maxn];int n,m,x,y,z,flag,tot,tot2,cnt;int last[maxn],size[maxn],fa[maxn],dep[maxn],son[maxn],w[maxn],top[maxn];void read(int &k){    int f=1;k=0;char c=getchar();    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();    k*=f;}void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}void dfs1(int x){    size[x]=1;    for(int i=last[x];i;i=e[i].pre)    {        int too=e[i].too;        if(too!=fa[x])        {            fa[too]=x;            dep[too]=dep[x]+e[i].sum;            dfs1(too);            if(size[too]>size[son[x]])son[x]=too;            size[x]+=size[too];        }    }}void dfs2(int x,int tp){    w[x]=++cnt;top[x]=tp;    if(son[x])dfs2(son[x],tp);    for(int i=last[x];i;i=e[i].pre)    if(e[i].too!=son[x]&&e[i].too!=fa[x])    dfs2(e[i].too,e[i].too);}void pushdown(int x){    if(a[x].tag==inf)return;    int tag=a[x].tag;a[x].tag=inf;    a[x<<1].tag=min(tag,a[x<<1].tag);    a[x<<1|1].tag=min(tag,a[x<<1|1].tag);}void update(int x,int nl,int nr,int l,int r,int delta){    ///if(nl!=nr)pushdown(x);    if(l<=nl&&nr<=r)a[x].tag=min(a[x].tag,delta);    else    {        //printf("%d %d\n",nl,nr);        int mid=(nl+nr)>>1;        if(l<=mid)update(x<<1,nl,mid,l,r,delta);        if(r>mid)update(x<<1|1,mid+1,nr,l,r,delta);    }}ll query(int x,int nl,int nr,int num){    if(nl!=nr)pushdown(x);    if(nl==num&&nr==num)return a[x].tag;    else    {        int mid=(nl+nr)>>1;        if(nl<=num&&num<=mid)return query(x<<1,nl,mid,num);        if(mid
          
           <=nr)return query(x<<1|1,mid+1,nr,num);    }}void work(int x,int y,int len){    int f1=top[x],f2=top[y];    while(f1!=f2)    {        if(dep[f1]
           
            >1; if(l!=r)build(x<<1,l,mid),build(x<<1|1,mid+1,r);}int main(){ read(n);read(m); for(int i=1;i<=m;i++) { read(x);read(y);read(z);read(flag); if(!flag)edge[++tot2].x=x,edge[tot2].y=y,edge[tot2].len=z; else add(x,y,z),add(y,x,z); } dfs1(1);dfs2(1,1);build(1,1,n); for(int i=1;i<=tot2;i++) work(edge[i].x,edge[i].y,edge[i].len+dep[edge[i].x]+dep[edge[i].y]); for(int i=2;i<=n;i++) { int ans=query(1,1,cnt,w[i]); if(ans!=inf)printf("%d ",ans-dep[i]); else printf("-1 "); } return 0;}
           
          
         
        
       
      

并查集：

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #define ll long longusing namespace std;void read(int &k){    int f=1;k=0;char c=getchar();    while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();    while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();    k*=f;}const int maxn=4010;struct zs{
    int too,sum,pre;}e[500010];struct poi{
    int x,y,len;}edge[500010];int n,m,x,y,z,flag,tot,tot2;int fq[maxn],fa[maxn],h[maxn],v[maxn],last[maxn];void add(int x,int y,int z){e[++tot].too=y;e[tot].sum=z;e[tot].pre=last[x];last[x]=tot;}void dfs(int x,int fa){    for(int i=last[x];i;i=e[i].pre)    if(e[i].too!=fa)h[e[i].too]=h[x]+e[i].sum,fq[e[i].too]=x,dfs(e[i].too,x);}bool cmp(poi a,poi b){
    return a.len