区间连区间

luogu P6348 [PA2011] Journeys 略带卡常

#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>e[4200001];
int dis[4200001],id[4200001];
int lson(int l)
{
    return l*2;
}
int rson(int l)
{
    return l*2+1;
}
void build(int rt,int l,int r,int n)
{
	e[rt+4*n].push_back(make_pair(rt,0));
	if(l==r)
	{
		id[l]=rt;
		return;
	}
	e[lson(rt)].push_back(make_pair(rt,0));
	e[rson(rt)].push_back(make_pair(rt,0));
	e[rt+4*n].push_back(make_pair(lson(rt)+4*n,0));
	e[rt+4*n].push_back(make_pair(rson(rt)+4*n,0));
	int mid=(l+r)/2;
	build(lson(rt),l,mid,n);
	build(rson(rt),mid+1,r,n);
}
void update(int rt,int l,int r,int L,int R,int pd,int n,int t)
{
	if(L<=l&&r<=R)
	{
		if(pd==0)
		{
			e[rt].push_back(make_pair(8*n+t,0));
		}
		else
		{
			e[8*n+t].push_back(make_pair(rt+4*n,1));
		}
		return;
	}
	int mid=(l+r)/2;
	if(L<=mid)
	{
		update(lson(rt),l,mid,L,R,pd,n,t);
	}
	if(mid<R)
	{
		update(rson(rt),mid+1,r,L,R,pd,n,t);
	}
}
void bfs(int p)
{
	int x,i;
	memset(dis,0x3f,sizeof(dis));
    deque<int> q;
    dis[id[p]]=0;
    q.push_back(id[p]);
    while(q.empty()==0)
    {
		x=q.front();
		q.pop_front();
		for(i=0;i<e[x].size();i++)
		{
			if(dis[e[x][i].first]>dis[x]+e[x][i].second)
			{
				dis[e[x][i].first]=dis[x]+e[x][i].second;
				if(e[x][i].second==1)
				{
					q.push_back(e[x][i].first);
				}
				else
				{
					q.push_front(e[x][i].first);
				}
			}
		}
	}
}
int main()
{
    int n,m,p,t=0,i,a,b,c,d;
    scanf("%d%d%d",&n,&m,&p);
    build(1,1,n,n);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        t++;
        update(1,1,n,a,b,0,n,t);
        update(1,1,n,c,d,1,n,t);
        t++;
        update(1,1,n,a,b,1,n,t);
        update(1,1,n,c,d,0,n,t);
    }
    bfs(p);
    for(i=1;i<=n;i++)
    {
        if(i==p)
        {
            printf("0\n");
        }
        else
        {
            printf("%d\n",dis[id[i]+4*n]);
        }
    }
    return 0;
}

点连点，点连区间

CF786B Legacy

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define sort stable_sort 
#define endl '\n'
vector<pair<ll,ll>>e[4200001];
ll dis[4200001],id[4200001],vis[4200001];
ll lson(ll l)
{
    return l*2;
}
ll rson(ll l)
{
    return l*2+1;
}
void build(ll rt,ll l,ll r,ll n)
{
	e[rt+4*n].push_back(make_pair(rt,0));
	if(l==r)
	{
		id[l]=rt;
		return;
	}
	e[lson(rt)].push_back(make_pair(rt,0));
	e[rson(rt)].push_back(make_pair(rt,0));
	e[rt+4*n].push_back(make_pair(lson(rt)+4*n,0));
	e[rt+4*n].push_back(make_pair(rson(rt)+4*n,0));
	ll mid=(l+r)/2;
	build(lson(rt),l,mid,n);
	build(rson(rt),mid+1,r,n);
}
void update(ll rt,ll l,ll r,ll L,ll R,ll pd,ll n,ll t)
{
	if(L<=l&&r<=R)
	{
		if(pd==0)
		{
			e[rt].push_back(make_pair(8*n+t,0));
		}
		else
		{
			e[8*n+t].push_back(make_pair(rt+4*n,pd));
		}
		return;
	}
	ll mid=(l+r)/2;
	if(L<=mid)
	{
		update(lson(rt),l,mid,L,R,pd,n,t);
	}
	if(mid<R)
	{
		update(rson(rt),mid+1,r,L,R,pd,n,t);
	}
}
void dijkstra(ll s)
{
    ll x,i;
	priority_queue<pair<ll,ll> >q;
	memset(dis,0x3f,sizeof(dis));
	dis[id[s]]=0;
    q.push(make_pair(0,id[s]));
	while(q.empty()==0)
	{
		x=q.top().second;
		q.pop();
		if(vis[x]==0)
		{
			vis[x]=1;
			for(i=0;i<e[x].size();i++)
			{
				if(dis[e[x][i].first]>dis[x]+e[x][i].second)
				{
					dis[e[x][i].first]=dis[x]+e[x][i].second;
					q.push(make_pair(-dis[e[x][i].first],e[x][i].first));
				}
			}
		}
	}
}
int main()
{
    ll n,m,p,t=0,i,a,b,c,d,pd,w;
	cin>>n>>m>>p;
    build(1,1,n,n);
    for(i=1;i<=m;i++)
    {
		cin>>pd;//某人因为这个位置调了一下午
		if(pd==1)
		{
			cin>>a>>c>>w;
			b=a;
			d=c;
			t++;
			update(1,1,n,a,b,0,n,t);
			update(1,1,n,c,d,w,n,t);
		}
		if(pd==2)
		{
			cin>>a>>c>>d>>w;
			b=a;
			t++;
			update(1,1,n,a,b,0,n,t);
			update(1,1,n,c,d,w,n,t);
		}
		if(pd==3)
		{
			cin>>a>>c>>d>>w;
			b=a;
			t++;
			update(1,1,n,c,d,0,n,t);
			update(1,1,n,a,b,w,n,t);
		}
    }
    dijkstra(p);
    for(i=1;i<=n;i++)
    {
        if(i==p)
        {
			cout<<"0 ";
        }
        else
        {
			if(dis[id[i]+4*n]==0x3f3f3f3f3f3f3f3f)
			{
				cout<<"-1 ";
			}
			else
			{
				cout<<dis[id[i]+4*n]<<" ";
			}
        }
    }
    return 0;
}