描述

　　精灵最近在农场上泛滥,它们经常会阻止牛们从农庄(牛棚_1)走到别的牛棚(牛_i的目的地是牛棚_i)。每一个精灵只认识牛_i并且知道牛_i一般走到牛棚_i的最短路经。所以它们在牛_i到牛棚_i之前的最后一条牛路上等牛_i。当然,牛不愿意遇到Gremlins,所以准备找一条稍微不同的路经从牛棚_1走到牛棚_i。所以,请你为每一头牛_i找出避免精灵的最短路经的长度。

　　和以往一样, 农场上的M (2 <= M <= 200,000)条双向牛路编号为1-M并且能让所有牛到达它们的目的地, N(3 <= N <= 100,000)个编号为1-N的牛棚.牛路i连接牛棚a_i (1 <= a_i <= N)和b_i (1 <= b_i <= N)并且需要时间t_i (1 <=t_i <= 1,000)通过。没有两条牛路连接同样的牛棚,所有牛路满足a_i!=b_i.在所有数据中,牛_i使用的牛棚_1到牛棚_i的最短路经是唯一的。

输入

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

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

输出

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

题解

　　智商不够，数据结构来凑。提供一个比较暴力的思路。

　　先搞出最短路树。我们考虑加入一条非树边，两端点为u、v，权值为w，如果它会影响点x的答案，那么x的答案会变成d[u]+d[v]+w-d[x]（d[x]为起点到x的最短路）。我们再考虑加入一条非树边会对哪些点产生影响：容易发现，会受影响的点是u到v的路径上出去lca的点。由于要使每个点的答案最小，所以这就是一个区间取min的问题，可以用树链剖分解决。放上代码：

#include<bits/stdc++.h>

using namespace std;

#define N 100010

#define INF 0x3f3f3f3f

int n,m;

int num=,f[N],vst[N<<];

struct node{

    int u,v,w,nxt;

}e[N<<];

void add(int u,int v,int w){e[++num]=(node){u,v,w,f[u]};f[u]=num;}

//build graph

#define pii pair<int,int>

#define mp make_pair

int d[N],vis[N];

void dijkstra(){

    memset(d,0x3f,sizeof(d));

    priority_queue<pii,vector<pii>,greater<pii> > q;

    d[]=;q.push(mp(d[],));

    while(!q.empty()){

        pii t=q.top();q.pop();

        int dd=t.first,u=t.second;

        if(vis[u]) continue;vis[u]=;

        for(int i=f[u];i;i=e[i].nxt){

            int v=e[i].v,w=e[i].w;

            if(d[v]>dd+w){d[v]=dd+w;q.push(mp(d[v],v));}

        }

    }

}

//shortest path

namespace TREE{

    int num,f[N];

    struct node{

        int u,v,nxt;

    }e[N<<];

    void add(int u,int v){

        e[++num]=(node){u,v,f[u]};f[u]=num;

        e[++num]=(node){v,u,f[v]};f[v]=num;

    }

    //build graph

    #define lc (p<<1)

    #define rc (p<<1|1)

    struct tree{

        int l,r,mx;

    }t[N<<];

    void up(int p){t[p].mx=max(t[lc].mx,t[rc].mx);}

    void now(int p,int v){t[p].mx=min(t[p].mx,v);}

    void down(int p){if(t[p].mx<INF) now(lc,t[p].mx),now(rc,t[p].mx);}

    void build(int p,int l,int r){

        t[p].l=l;t[p].r=r;

        if(l==r){t[p].mx=INF;return;}

        int mid=(l+r)>>;

        build(lc,l,mid);build(rc,mid+,r);up(p);

    }

    void update(int p,int l,int r,int v){

        if(v>=t[p].mx||l>r) return;

        if(l<=t[p].l&&t[p].r<=r){now(p,v);return;}

        int mid=(t[p].l+t[p].r)>>;down(p);

        if(l<=mid) update(lc,l,r,v);

        if(r> mid) update(rc,l,r,v);

        up(p);

    }

    int query(int p,int k){

        if(t[p].l==t[p].r){return t[p].mx;}

        int mid=(t[p].l+t[p].r)>>;down(p);

        if(k<=mid) return query(lc,k);

        else return query(rc,k);

    }

    //segment tree

    int cnt,dep[N],faz[N],seg[N],siz[N],son[N],top[N];

    void dfs1(int u,int fa,int d){

        dep[u]=d;faz[u]=fa;siz[u]=;

        for(int i=f[u];i;i=e[i].nxt){

            int v=e[i].v;

            if(v==fa) continue;

            dfs1(v,u,d+);siz[u]+=siz[v];

            if(siz[v]>siz[son[u]]) son[u]=v;

        }

    }

    void dfs2(int u,int st){

        seg[u]=++cnt;top[u]=st;

        if(!son[u]) return;dfs2(son[u],st);

        for(int i=f[u];i;i=e[i].nxt){

            int v=e[i].v;

            if(v==faz[u]||v==son[u]) continue;

            dfs2(v,v);

        }

    }

    void change(int x,int y,int v){

        int xx=top[x],yy=top[y];

        while(xx^yy){

            if(dep[xx]<dep[yy]){swap(xx,yy);swap(x,y);}

            update(,seg[xx],seg[x],v);

            x=faz[xx];xx=top[x];

        }

        if(dep[x]>dep[y]) swap(x,y);

        update(,seg[x]+,seg[y],v);

    }

    //tree dissection

}

int main(){

    int x,y,z;

    scanf("%d%d",&n,&m);

    for(int i=;i<=m;i++){scanf("%d%d%d",&x,&y,&z);add(x,y,z);add(y,x,z);}

    dijkstra();

    for(int i=;i<=num;i+=){

        int u=e[i].u,v=e[i].v,w=e[i].w;

        if(d[u]+w==d[v]||d[v]+w==d[u]){TREE::add(u,v);vst[i]=vst[i^]=;}

    }

    TREE::dfs1(,,);TREE::dfs2(,);TREE::build(,,n);

    for(int i=;i<=num;i+=){

        if(vst[i]) continue;

        int u=e[i].u,v=e[i].v,w=e[i].w,tmp=d[u]+d[v]+w;

        TREE::change(u,v,tmp);

    }

    for(int i=;i<=n;i++){

        int ans=TREE::query(,TREE::seg[i]);

        if(ans==INF) puts("-1");

        else printf("%d\n",ans-d[i]);

    }

    return ;

}

巴特西

WOJ#2423 安全出行Safe Travel

描述

输入

输出

最新文章

热门文章