bzoj 1576: [Usaco2009 Jan]安全路经Travel 树链剖分

1576: [Usaco2009 Jan]安全路经Travel

Time Limit: 10 Sec  Memory Limit: 64 MB

Submit: 665  Solved: 227
[Submit][Status]

Description

Input

* 第一行: 两个空格分开的数, N和M

* 第2..M+1行: 三个空格分开的数a_i, b_i,和t_i

Output

* 第1..N-1行: 第i行包含一个数:从牛棚_1到牛棚_i+1并且避免从牛棚1到牛棚i+1最短路经上最后一条牛路的最少的时间.如果这样的路经不存在,输出-1.

Sample Input

4 5
1 2 2
1 3 2
3 4 4
3 2 1
2 4 3

输入解释:

跟题中例子相同

Sample Output

3
3
6

输出解释:

跟题中例子相同

HINT

 

Source

Gold

　　这道题本来的思路是对于每个子树维护一个单调队列，但是看着写链剖都能T的那么惨，还是老老实实写链剖吧。

　　这道题给我最大的启示是：最短路用spfa是非常作死的。。。。。不过以前我都默认spfa最坏为nlogn的。

　　至少我一整个下午都没有想到usaco的题居然还要卡spfa。

 

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110000
#define MAXQ MAXN*20
#define MAXE (MAXN*4 +MAXN*2)
#define MAXV MAXN
#define INF 0x3f3f3f3f
#define lch (now<<1)
#define rch (now<<1^1)
int n,m;
inline int nextInt()
{
        register int x=0;
        register char ch;
        while (ch=getchar(),ch<'0' || ch>'9');
        while (x=x*10+ch-'0',ch=getchar(),ch<='9' && ch>='0');
        return x;
}
struct sgt_node
{
        int l,r,val,lazy;
}sgt[MAXN*4];
inline void down(int now)
{
        sgt[lch].val=min(sgt[lch].val,sgt[now].val);
        sgt[rch].val=min(sgt[rch].val,sgt[now].val);
}
void Build_sgt(int now,int l,int r)
{
        sgt[now].l=l;sgt[now].r=r;
        if (sgt[now].l==sgt[now].r)
        {
                sgt[now].val=INF;
                return ;
        }
        Build_sgt(lch,l,(l+r)>>1);
        Build_sgt(rch,((l+r)>>1)+1,r);
        sgt[now].val=max(sgt[lch].val,sgt[rch].val);
}
void Modify_sgt(int now,int l,int r,int v)
{
        if (sgt[now].l==l && sgt[now].r==r)
        {
                sgt[now].val=min(sgt[now].val,v);
                return ;
        }
        down(now);
        int mid=(sgt[now].l+sgt[now].r)>>1;
        if (r<=mid)
                Modify_sgt(lch,l,r,v);
        else if (mid<l)
                Modify_sgt(rch,l,r,v);
        else
                Modify_sgt(lch,l,mid,v),Modify_sgt(rch,mid+1,r,v);
}
int Query_sgt(int now,int pos)
{
        if (sgt[now].l==sgt[now].r)return sgt[now].val;
        if (pos<=((sgt[now].l+sgt[now].r)>>1))
                return min(sgt[now].val,Query_sgt(lch,pos));
        else
                return min(sgt[now].val,Query_sgt(rch,pos));
}
struct Edge
{
        int np,val;
        Edge *next;
        Edge *neg;
}E[MAXE],*V[MAXV],*V2[MAXV];
int tope=-1;
inline void addedge(int x,int y,int z)
{
        E[++tope].np=y;
        E[tope].val=z;
        E[tope].next=V[x];
        V[x]=&E[tope];
}
inline void addedge2(int x,int y,int z)
{
        E[++tope].np=y;
        E[tope].val=z;
        E[tope].next=V2[x];
        V2[x]=&E[tope];
}
int q[MAXQ];
bool vis[MAXN];
int pnt[MAXN];
int dis[MAXN];
Edge *pne[MAXN];
/*
void spfa(register int now)
{
        register int head=-1,tail=0;
        memset(dis,INF,sizeof(dis));
        q[0]=now;
        dis[now]=0;
        register Edge *ne;
        while (head!=tail)
        {
                head++;
                if (head==MAXQ)head=0;
                now=q[head];
                vis[now]=false;
                for (ne=V[now];ne;ne=ne->next)
                {
                        if (dis[ne->np]>dis[now]+ne->val)
                        {
                                dis[ne->np]=dis[now]+ne->val;
                                pne[ne->np]=ne->neg;
                                pnt[ne->np]=now;
                                if (!vis[ne->np])
                                {
                                        tail++;
                                        if (tail==MAXQ)tail=0;
                                        q[tail]=ne->np;
                                        vis[ne->np]=true;
                                }
                        }
                }
        }
}*/
pair<int,int> h[MAXQ];
void dijkstrea(int now)
{
        memset(dis,INF,sizeof(dis));
        dis[now]=0;
        int toph=0;
        Edge *ne;
        h[toph]=make_pair(-0,now);
        push_heap(h,h+(++toph));
        while (~toph)
        {
                if (h[0].first!=-dis[h[0].second])
                {
                        pop_heap(h,h+(toph--));
                        continue;
                }
                for (ne=V[h[0].second];ne;ne=ne->next)
                {
                        if (dis[ne->np]>dis[h[0].second] + ne->val)
                        {
                                dis[ne->np]=dis[h[0].second]+ne->val;
                                pnt[ne->np]=h[0].second;
                                pne[ne->np]=ne->neg;
                                h[toph]=make_pair(-dis[ne->np],ne->np);
                                push_heap(h,h+(++toph));
                        }
                }
                pop_heap(h,h+(toph--));
        }
}
int son[MAXN];
int top[MAXN];
int depth[MAXN];
int pos[MAXN],dfstime=0;
int dfs1(int now)
{
        register Edge *ne;
        int mxsiz=0;
        int siz=1,t;
        for (ne=V2[now];ne;ne=ne->next)
        {
                depth[ne->np]=depth[now]+1;
                siz+=t=dfs1(ne->np);
                if (t>mxsiz)
                {
                        mxsiz=t;
                        son[now]=ne->np;
                }
        }
        return siz;
}
void dfs2(int now,int tp)
{
        register Edge *ne;
        pos[now]=++dfstime;
        top[now]=tp;
        if (~son[now])
                dfs2(son[now],tp);
        for (ne=V2[now];ne;ne=ne->next)
        {
                if (ne->np==son[now])continue;
                dfs2(ne->np,ne->np);
        }
}
int lca(register int x,register int y)
{
        while (x!=y)
        {
                if (top[x]==top[y])
                {
                        if (depth[x]<depth[y])return x;
                        else return y;
                }
                if (depth[top[x]]<depth[top[y]])swap(x,y);
                x=pnt[top[x]];
        }
        return x;
}
void work()
{
        register Edge *ne;
        register int now,i,d,t;
        for (i=2;i<=n;i++)
        {
                for(ne=V[i];ne;ne=ne->next)
                {
                        now=i;
                        if (ne==pne[now])continue;
                        d=dis[ne->np]+ne->val  +dis[now];
                        t=lca(ne->np,now);
                        if (t==now)continue;
                        while (true)
                        {
                                if (depth[top[now]]==depth[top[t]])
                                {
                                        if (pos[t]+1<=pos[now])
                                                Modify_sgt(1,pos[t]+1,pos[now],d);
                                        break;
                                }
                                Modify_sgt(1,pos[top[now]],pos[now],d);
                                now=pnt[top[now]];
                        }
                }
        }
        int ans;
        for (i=2;i<=n;i++)
        {
                ans=-dis[i]+Query_sgt(1,pos[i]);
                if (ans+dis[i]==INF)
                        printf("-1
");
                else
                        printf("%d
",ans);
        }
}
int main()
{
        freopen("input.txt","r",stdin);
        //freopen("output.txt","w",stdout);
        int i,j,k,x,y,z;
        n=nextInt();m=nextInt();
        for (i=0;i<m;i++)
        {
                x=nextInt(),y=nextInt(),z=nextInt();
                addedge(x,y,z);
                addedge(y,x,z);
                V[x]->neg=V[y];
                V[y]->neg=V[x];
        }
        dijkstrea(1);
        memset(son,-1,sizeof(son));
        for (i=2;i<=n;i++)
                addedge2(pnt[i],i,INF);
        dfs1(1);
        dfs2(1,1);
        Build_sgt(1,1,dfstime);
        work();
}