第一次学习这个，思路就是建两棵线段树，一棵入树一棵出树，依据这样的思想自己打了代码

#include <bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
typedef pair<long long,int> pii;
int n,q,s,leaf[maxn];
const long long inf=0x3f3f3f3f3f3f3f3f;
const int half=maxn*4;
vector<pii> g[maxn*9];
long long dis[maxn*9];

struct seg_tree{
	int l,r;
}tree[maxn*4];

void build(int o,int l,int r){//小于half为入树，大于half为出树
	tree[o].l=l,tree[o].r=r;
	if(l==r){
		g[o].push_back(make_pair(0,o+half));
		g[o+half].push_back(make_pair(0,o));
		leaf[l]=o;
		return;
	}
	int mid=(l+r)>>1;
	g[o].push_back(make_pair(0,o<<1|1));
	g[o].push_back(make_pair(0,o<<1));
	g[half+(o<<1|1)].push_back(make_pair(0,half+o));
	g[half+(o<<1)].push_back(make_pair(0,half+o));
	build(o<<1,l,mid);
	build(o<<1|1,mid+1,r);
}

void update(int o,int l,int r,int u,int in,long long w){
	if(tree[o].l>=l&&tree[o].r<=r){
		if(in==0){
			g[leaf[u]+half].push_back(make_pair(w,o));
			return;
		}else{
			g[o+half].push_back(make_pair(w,leaf[u]));
			return;
		}
	}
	if(tree[o<<1].r>=l) update(o<<1,l,r,u,in,w);
	if(tree[o<<1|1].l<=r) update(o<<1|1,l,r,u,in,w);
	return;
}

void dijkstra(){
	memset(dis,0x3f,sizeof dis);
	priority_queue<pii,vector<pii> > q;
	q.push(make_pair(0,leaf[s]));
	dis[leaf[s]]=0;
	while(!q.empty()){
		pii p=q.top();
		q.pop();
		long long u=p.second,w=-p.first;
		if(dis[u]!=w) continue;
		for(int i=0;i<g[u].size();i++){
			long long v=g[u][i].second,k=g[u][i].first;
			if(dis[u]+k<dis[v]){
				dis[v]=dis[u]+k;
				q.push(make_pair(-dis[v],v));
		    }
		}
	}
}

int main(){
	scanf("%d%d%d",&n,&q,&s);
	build(1,1,n);
	for(int i=1;i<=q;i++){
		int op;
		scanf("%d",&op);
		if(op==1){
			int v,u;
			long long w;
			scanf("%d%d%lld",&v,&u,&w);
			g[leaf[v]].push_back(make_pair(w,leaf[u]));
		}else if(op==2){
			int v,l,r;
			long long w;
			scanf("%d%d%d%lld",&v,&l,&r,&w);
			update(1,l,r,v,0,w);
		}else{
			int v,l,r;
			long long w;
			scanf("%d%d%d%lld",&v,&l,&r,&w);
			update(1,l,r,v,1,w);
		}
	}
	dijkstra();
	/*for(int i=1+half;i<=4*n+half;i++){
		for(int j=0;j<g[i].size();j++){
			int u=i;
			int v=g[u][j].second;
			int k=g[u][j].first;
			cout<<u<<" "<<v<<" "<<k<<endl;
		}
	}*/
	for(int i=1;i<=n;i++){
		if(dis[leaf[i]]==inf) printf("-1 ");
		else printf("%lld ",dis[leaf[i]]);
	}
} 

然而这样子 wa了第七个点。

将函数update中g[leaf[u]+half].push_back(make_pair(w,o)); 改为g[leaf[u]].push_back(make_pair(w,o)); 则AC本题。 求问为什么操作2不能将出树的叶子节点连向入树的区间？还是我别的建图有问题？