原题链接
考察:线段树+最短路
思路:
线段树优化建边的模板题,基本参考了大佬博客,私以为这个是讲得最好的. GO
关于为什么出树是由子到父,因为入树必然是父节点到子节点,而为了搭配入树只能是子节点到父节点.
Code
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL,int> PII;
const int N = 100010;
int n,q,s,idx,h[N<<3],tot,pos[2][N];
bool st[N<<3];
LL dist[N<<3];
struct Road{
int to,ne,w;
}road[N*28];
struct Node{
int l,r,nums;
}tr[2][N<<2];
void add(int a,int b,int c)
{
road[idx].w = c,road[idx].to = b,road[idx].ne = h[a],h[a] = idx++;
}
void build(int u,int l,int r,int s)
{
tr[s][u] = {l,r,++tot};
if(l==r)
{
pos[s][l] = tr[s][u].nums;
return;
}
int mid = l+r>>1;
build(u<<1,l,mid,s); build(u<<1|1,mid+1,r,s);
if(!s)
{
add(tr[s][u].nums,tr[s][u<<1].nums,0);
add(tr[s][u].nums,tr[s][u<<1|1].nums,0);
return;
}
add(tr[s][u<<1].nums,tr[s][u].nums,0);
add(tr[s][u<<1|1].nums,tr[s][u].nums,0);
}
void add_s_I(int u,int idx,int l,int r,int w)
{
if(tr[1][u].l>=l&&tr[1][u].r<=r)
{
add(pos[1][idx],tr[0][u].nums,w);
return;
}
int mid = tr[0][u].l+tr[0][u].r>>1;
if(l<=mid) add_s_I(u<<1,idx,l,r,w);
if(mid<r) add_s_I(u<<1|1,idx,l,r,w);
}
void add_I_s(int u,int l,int r,int idx,int w)
{
if(tr[1][u].l>=l&&tr[1][u].r<=r)
{
add(tr[1][u].nums,pos[0][idx],w);
return;
}
int mid = tr[1][u].l+tr[1][u].r>>1;
if(l<=mid) add_I_s(u<<1,l,r,idx,w);
if(mid<r) add_I_s(u<<1|1,l,r,idx,w);
}
void dijkstra(int s)
{
priority_queue<PII,vector<PII>,greater<PII> > q;
for(int i=0;i<=tot;i++) dist[i] = 1e14;
dist[s] = 0;
q.push({0,s});
while(q.size())
{
PII it = q.top();
q.pop();
int u = it.second;
if(st[u]) continue;
st[u] =1;
for(int i=h[u];~i;i=road[i].ne)
{
int v = road[i].to;
if(dist[v]>dist[u]+road[i].w)
{
dist[v] = dist[u]+road[i].w;
q.push({dist[v],v});
}
}
}
for(int i=1;i<=n;i++)
if(dist[pos[0][i]]==1e14) printf("-1 ");
else printf("%lld ",dist[pos[0][i]]);
printf("\n");
}
int main()
{
scanf("%d%d%d",&n,&q,&s);
memset(h,-1,sizeof h);
build(1,1,n,0);//入树
build(1,1,n,1);//出树
while(q--)
{
int t,u,l,r,w;
scanf("%d",&t);
if(t==1)
{
scanf("%d%d%d",&u,&l,&w);
add(pos[1][u],pos[0][l],w);
}else if(t==2){
scanf("%d%d%d%d",&u,&l,&r,&w);
add_s_I(1,u,l,r,w);
}else if(t==3){
scanf("%d%d%d%d",&u,&l,&r,&w);
add_I_s(1,l,r,u,w);
}
}
for(int i=1;i<=n;i++)
{
add(pos[0][i],pos[1][i],0);
add(pos[1][i],pos[0][i],0);
}
dijkstra(pos[1][s]);
return 0;
}