hdu 5669 Road

题目大意

\(n\)个点,\(m\)次连边

每次连边为\((a\sim b)\leftrightarrow (c\sim d),cost=w\)

即在\((a-b)\)区间内的点向\((c-d)\)区间内的点，两两连一条费用w的双向边

给出\(k\)次机会使一条边费用为\(0\)

求\(1-n\)的最短路

分析

暴力连边\(O(mn^2)\)显然不行

既然是区间连边，是否可以用线段树的方法把区间拆成log个呢

做法

考虑一颗线段树

每次把提取出的\(log\)个区间\(log^2\)连边

然后考虑走到一个线段上

如果线段上每一个点都在当前到达集合，那么可以往下走

由于父亲一定包含当前点，所以可以往上走

但这样分类讨论难以实现

考虑两棵线段树

连边第一颗树连向第二棵树

第一棵树只能往上走

第二棵树只能往下走

然后第二棵树上的线段连一条边指回第一棵树的对应节点

源点放在第一棵树

汇点放在第二棵树

可以发现，跳完一条边后即到了第二棵树，此时线段上每个点都在可达集合，可以往下走，然后跳回第一棵树，继续走边

是符合要求的

最后考虑回一开始的连边，\(log^2\)的连边跑起dijkstra还是很炸的

但是我们可以强行加一个中间节点，这样边数就变成\(log\)了

连完边跑分层图最短路即可

连边复杂度\(O(m\log n)\)

dijkstra复杂度\(O(m\log^2 n)\)

solution(代码较挫)

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cctype>

#include <cmath>

#include <queue>

using namespace std;

const int M=131077;

const int N=890035;

const int INF=2139062143;

inline int ri(){

    int x=0;bool f=1;char c=getchar();

    for(;!isdigit(c);c=getchar()) if(c=='-') f=0;

    for(;isdigit(c);c=getchar()) x=x*10+c-48;

    return f?x:-x;

}

int tcas,n,m,lim,id,S,T;

struct vec{

    int g[M<<2],te;

    struct edge{

        int y,d,nxt;

        edge(int _y=0,int _d=0,int _nxt=0){y=_y,d=_d,nxt=_nxt;}

    }e[N];

    vec(){memset(g,0,sizeof g);te=0;}

    inline void push(int x,int y,int d=0){e[++te]=edge(y,d,g[x]);g[x]=te;}

    inline int& operator () (int x){return g[x];}

    inline edge& operator [] (int x){return e[x];}

}e;

struct segment{

    int lc[M<<1],rc[M<<1],fa[M<<1],tot,rt;

    segment(){

        memset(lc,0,sizeof lc);

        memset(rc,0,sizeof rc);

        tot=0;rt=0;

    }

    int build(int l,int r){

        int x=++tot;

        if(l==r) return x;

        int mid=l+r>>1;

        lc[x]=build(l,mid);

        rc[x]=build(mid+1,r);

        fa[lc[x]]=x;

        fa[rc[x]]=x;

        return x;

    }

    int find(int x,int l,int r,int to){

        if(l==r) return x;

        int mid=l+r>>1;

        if(to<=mid) return find(lc[x],l,mid,to);

        return find(rc[x],mid+1,r,to);

    }

    int find(int x){return find(rt,1,n,x);}

    void toid(int x,int l,int r,int tl,int tr,int id,int d){

        if(tl<=l&&r<=tr){

            e.push(x,id,d);

            return;

        }

        int mid=l+r>>1;

        if(tl<=mid) toid(lc[x],l,mid,tl,tr,id,d);

        if(mid<tr) toid(rc[x],mid+1,r,tl,tr,id,d);

    }

    void idto(int x,int l,int r,int tl,int tr,int id,int d){

        if(tl<=l&&r<=tr){

            e.push(id,x,d);

            return;

        }

        int mid=l+r>>1;

        if(tl<=mid) idto(lc[x],l,mid,tl,tr,id,d);

        if(mid<tr) idto(rc[x],mid+1,r,tl,tr,id,d);

    }

    void toid(int l,int r,int id,int d){

        toid(rt,1,n,l,r,id,d);

    }

    void idto(int l,int r,int id,int d){

        idto(rt,1,n,l,r,id,d);

    }

}L,R;

void addedge(int u,int v,int x,int y,int d){

    ++id;

    L.toid(u,v,id,d);

    R.idto(x,y,id,0);

}

struct node{

    int s,x,d;

    node(int _s=0,int _x=0,int _d=0){s=_s,x=_x,d=_d;}

    bool operator < (const node &y) const{

        return d>y.d;

    }

};

priority_queue<node>q;

int f[13][M<<2];

void solve(){

    memset(f,127,sizeof f);

    f[0][S]=0;

    q.push(node(0,S,0));

    node nw;

    int s,x,d,p,y;

    while(!q.empty()){

        nw=q.top(); q.pop();

        s=nw.s; x=nw.x; d=nw.d;

        for(p=e(x);p;p=e[p].nxt){

            y=e[p].y;

            if(d+e[p].d<f[s][y]){

                f[s][y]=d+e[p].d;

                q.push(node(s,y,f[s][y]));

            }

            if(s<lim&&d<f[s+1][y]){

                f[s+1][y]=d;

                q.push(node(s+1,y,f[s+1][y]));

            }

        }

    }

    int i,ans=INF;

    for(i=0;i<=lim;i++) ans=min(ans,f[i][T]);

    if(ans==INF) puts("Yww is our red sun!");

    else printf("%d\n",ans);

}

int main(){

    int i,u,v,x,y,d;

    tcas=ri();

    n=ri(),m=ri(),lim=ri();

    L.tot=0; L.build(1,n); L.rt=1;

    R.tot=L.tot; R.build(1,n); R.rt=L.tot+1;

    S=L.find(1); T=R.find(n); id=R.tot;

    for(i=L.rt+1;i<=L.tot;i++) e.push(i,L.fa[i]);

    for(i=R.rt;i<=R.tot;i++) e.push(i,i-L.tot);

    for(i=R.rt+1;i<=R.tot;i++) e.push(R.fa[i],i);

    while(m--){

        u=ri(),v=ri(),x=ri(),y=ri(),d=ri();

        addedge(u,v,x,y,d);

        addedge(x,y,u,v,d);

    }

    solve();

    return 0;

}

巴特西

hdu 5669 Road

题目大意

分析

做法

solution(代码较挫)

最新文章

热门文章