在题目要求要无向边时（即双向边），出树和入树父亲结点与儿子结点之间边的方向不变，若点连向区间时直接操作即可，例如从区间a到点b，参照2.2的图即可，但是如果是区间连向区间，需要建虚拟结点的话，还是应当多建虚拟节点，不能用原有虚拟节点去连双向边。例如，区间a到区间b连无向边，从a连向b需要建立两个虚拟结点，从b再连向a需要再建立两个虚拟节点，否则，会出现原来题目中没有出现的边，导致最短路出错。切忌！
3例题 3.1 洛谷CF786Bhttps://www.luogu.com.cn/problem/CF786B
裸题，连完边跑dij即可。具体实现如下：
代码：
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<sstream> #include<queue> #include<map> #include<vector> #include<set> #include<deque> #include<cstdlib> #include<ctime> #define dd double #define ld long double #define ll long long #define ull unsigned long long #define N 900010 #define M 9000090 using namespace std; const ll INF=0x3f3f3f3f; struct edge{ ll to,next,w; inline void intt(ll to_,ll next_,ll w_){ to=to_;next=next_;w=w_; } }; edge li[M];ll head[N],tail; inline void add(ll from,ll to,ll w){ li[++tail].intt(to,head[from],w); head[from]=tail; } ll n,q,s; struct rode{ ll l,r; }; rode p[N]; inline void build(ll k,ll l,ll r){ p[k].l=l;p[k].r=r; if(l==r){ add(l+8*n,k,0);add(k+4*n,l+8*n,0); add(k,l+8*n,0);add(l+8*n,k+4*n,0); return; } add(k,k*2,0);add(k*2+n*4,k+n*4,0); add(k,k*2+1,0);add(k*2+1+n*4,k+n*4,0); ll mid=l+r>>1; build(k*2,l,mid);build(k*2+1,mid+1,r); } inline void addh(ll k,ll z,ll y,ll pd,ll u,ll w){ ll l=p[k].l,r=p[k].r,mid=l+r>>1; if(l==z&&y==r){ if(!pd) return add(u+8*n,k,w); else return add(k+4*n,u+8*n,w); } if(y<=mid) addh(k*2,z,y,pd,u,w); else if(z>mid) addh(k*2+1,z,y,pd,u,w); else addh(k*2,z,mid,pd,u,w),addh(k*2+1,mid+1,y,pd,u,w); } struct DIJ{ ll d[N];bool vis[N]; struct node{ ll to,w; node() {} node(ll to,ll w) : to(to),w(w) {} }; struct cmp{ inline bool operator () (node a,node b){ return a.w>b.w; } }; priority_queue<node,vector<node>,cmp> q; inline void Dij(ll s){ memset(d,INF,sizeof(d)); d[s]=0; q.push(node(s,0)); while(!q.empty()){ node fr=q.top();q.pop(); if(vis[fr.to]) continue; vis[fr.to]=1; for(int k=head[fr.to];k;k=li[k].next){ ll to=li[k].to; if(!vis[to]&&d[to]>d[fr.to]+li[k].w){ d[to]=d[fr.to]+li[k].w; q.push(node(to,d[to])); } } } } }; DIJ dij; int main(){ scanf("%lld%lld%lld",&n,&q,&s); build(1,1,n); for(ll i=1;i<=q;i++){ ll op,v,u,w,l,r; scanf("%lld",&op); if(op==1){ scanf("%lld%lld%lld",&v,&u,&w); add(v+8*n,u+8*n,w); } else if(op==2){ scanf("%lld%lld%lld%lld",&v,&l,&r,&w); addh(1,l,r,0,v,w); } else if(op==3){ scanf("%lld%lld%lld%lld",&v,&l,&r,&w); addh(1,l,r,1,v,w); } } s+=8*n; dij.Dij(s); for(int i=1;i<=n;i++){ printf("%lld ",dij.d[i+8*n]<=4e18?dij.d[i+8*n]:-1); } return 0; } 3.2 洛谷P6348是区间连向区间的例题，注意虚拟节点不能乱用即可，虚拟节点的编号为k+9*n。
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<cstring> #include<sstream> #include<queue> #include<map> #include<vector> #include<set> #include<deque> #include<cstdlib> #include<ctime> #define ld long double #define ll long long #define ull unsigned long long #define N 9000100 #define M 10001000 using namespace std; const ll INF=0x3f3f3f3f; struct edge{ ll next,to,w; inline void intt(ll to_,ll next_,ll w_){ next=next_;to=to_;w=w_; } }; edge li[M];ll head[N],tail; inline void add(ll from,ll to,ll w){ li[++tail].intt(to,head[from],w); head[from]=tail; } ll p[N],n,m,s; inline void build(ll k,ll l,ll r){ if(l==r){ add(k,l+8*n,0);add(l+8*n,k,0); add(k+4*n,l+8*n,0);add(l+8*n,k+4*n,0); return; } add(k,k*2,0);add(k,k*2+1,0); add(k*2+4*n,k+4*n,0);add(k*2+1+4*n,k+4*n,0); ll mid=l+r>>1; build(k*2,l,mid);build(k*2+1,mid+1,r); } inline void addh(ll k,ll l,ll r,ll z,ll y,ll pd,ll u,ll w){ if(l==z&&r==y){ if(!pd) return add(u,k,w); else return add(k+4*n,u,w); } ll mid=l+r>>1; if(y<=mid) addh(k*2,l,mid,z,y,pd,u,w); else if(z>mid) addh(k*2+1,mid+1,r,z,y,pd,u,w); else addh(k*2,l,mid,z,mid,pd,u,w),addh(k*2+1,mid+1,r,mid+1,y,pd,u,w); } deque<ll> q;ll d[N]; bool vis[N]; inline void dfs(ll s){ memset(d,INF,sizeof(d)); q.push_front(s);d[s]=0; while(q.size()){ ll top=q.front();q.pop_front(); if(vis[top]) continue; vis[top]=1; for(ll k=head[top];k;k=li[k].next){ ll to=li[k].to; if(vis[to]) continue; if(d[to]>d[top]+li[k].w){ d[to]=d[top]+li[k].w; if(li[k].w) q.push_back(to); else q.push_front(to); } } } } int main(){ scanf("%lld%lld%lld",&n,&m,&s); build(1,1,n); ll tailx=9*n; for(ll i=1;i<=m;i++){ ll a,b,c,dd; scanf("%lld%lld%lld%lld",&a,&b,&c,&dd); addh(1,1,n,a,b,1,++tailx,0); addh(1,1,n,c,dd,0,++tailx,0); add(tailx-1,tailx,1); addh(1,1,n,c,dd,1,++tailx,0); addh(1,1,n,a,b,0,++tailx,0); add(tailx-1,tailx,1); } dfs(s+8*n); for(ll i=1;i<=n;i++) printf("%lld\n",d[i+8*n]); return 0; }