Legacy(线段树优化建图模板)

题目链接

https://codeforces.com/contest/786/problem/B

题目大意

n个点,q次连边,起始位置是s,每次连边有三种连法,点到点,区间到点,点到区间,问从s开始到其他点的最短路。

解题思路

线段树优化建图后跑最短路

线段树优化建图

优化点到区间连边且权值相等,区间到点连边且权值相等,区间到区间建边且权值相等的问题。

代码

#include <bits/stdc++.h>
const int maxn=112345;
const int maxv=maxn*5;
using namespace std;
typedef long long LL;
#define mpi make_pair
const long long INF=99999999999999999;
int id[2][maxn<<2],idx;
vector<pair<int,int> >g[maxv];
int n,q,s;
void addedge(int u,int v,int w)
{
    g[u].push_back(make_pair(v,w));
}
void build(int x,int l,int r,int k)//k==0 in;k==1 out;
{
    id[k][x]=++idx;
    if(l==r)
    {
        if(k==0)
            addedge(id[k][x],l,0);//入树虚拟节点向原始节点l连边
        else
            addedge(l,id[k][x],0);//原始节点l向出数虚拟节点连边
        return;
    }
    int mid=(l+r)>>1;
    build(x<<1,l,mid,k);
    build(x<<1|1,mid+1,r,k);
    if(k==0)//入树父亲向孩子连边
    {
        addedge(id[k][x],id[k][x<<1],0);
        addedge(id[k][x],id[k][x<<1|1],0);
    }
    else//出树孩子向父亲连边
    {
        addedge(id[k][x<<1],id[k][x],0);
        addedge(id[k][x<<1|1],id[k][x],0);
    }
}
vector<int>vs;
void get(int x,int l,int r,int ll,int rr,int k)//将区间内的节点编号push进vs里
{
    if(ll<=l&&r<=rr)
    {
        vs.push_back(id[k][x]);
        return;
    }
    int mid=(l+r)>>1;
    if(ll<=mid)
        get(x<<1,l,mid,ll,rr,k);
    if(rr>mid)
        get(x<<1|1,mid+1,r,ll,rr,k);
}
bool vis[maxv];
long long dis[maxv];
void dij(int s)
{
    for(int i=1; i<=5*n; i++)//要开5倍,4倍线段树加本身
        vis[i]=0,dis[i]=INF;
    priority_queue<pair<long long,int> >q;
    q.push(mpi(0,s));
    dis[s]=0;
    while(!q.empty())
    {
        int u=q.top().second;
        q.pop();
        if(vis[u])
            continue;
        vis[u]=1;
        for(int i=0; i<g[u].size(); i++)
        {
            int v=g[u][i].first,c=g[u][i].second;
            if(dis[v]>dis[u]+c)
            {
                dis[v]=dis[u]+c;
                q.push(mpi(-dis[v],v));
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>q>>s;
    idx=n;
    build(1,1,n,0);//建两颗线段树一颗入树一颗出树
    build(1,1,n,1);
    for(int i=0; i<q; i++)
    {
        int t;
        cin>>t;
        if(t==1)
        {
            int v,u,w;
            cin>>v>>u>>w;
            addedge(v,u,w);
        }
        else if(t==2)//点到区间
        {
            vs.clear();
            int v,l,r,w;
            cin>>v>>l>>r>>w;
            get(1,1,n,l,r,0);//获取到区间内压缩的点后
            for(int i=0; i<vs.size(); i++)//将v与压缩的点连边
            {
                addedge(v,vs[i],w);
            }
        }
        else//区间到点
        {
            vs.clear();
            int v,l,r,w;
            cin>>v>>l>>r>>w;
            get(1,1,n,l,r,1);//与上面同理
            for(int i=0; i<vs.size(); i++)
            {
                addedge(vs[i],v,w);
            }
        }
    }
    dij(s);
    for(int i=1; i<=n; i++)
    {
        if(dis[i]==INF)
            dis[i]=-1;
        cout<<dis[i]<<" ";
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注