标签：rt int ll back pair 建图 push 线段 模板
区间连区间
#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;
}
点连点，点连区间
#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;
}
标签：rt,
int,
ll,
back,
pair,
建图,
push,
线段,
模板
From： https://www.cnblogs.com/The-Shadow-Dragon/p/17572381.html