好久不写题解了QAQ
传送门：https://www.luogu.org/problemnew/show/CF786B
很巧妙的一道题
考虑建两颗线段树，一颗out,维护出去的边，一颗in,维护进来的边
这样的话，所有的加进来的边，都是从out连向in,而且最后的最短路，实际上求得是out中的点到in中的点的最短路（虽然代码上体现不出）
in,out中的连边方式，也是考虑上述结论得出的
代码：
#include#include #include #include #include #include #include using namespace std;#define ll long long inline int read(){ int ans = 0,op = 1; char ch = getchar(); while(ch < '0' || ch > '9') { if(ch == '-') op = -1; ch = getchar(); } while(ch >= '0' && ch <= '9') { (ans *= 10) += ch - '0'; ch = getchar(); } return ans * op;}const int maxn = 2e5 + 5;struct node{ int to,cost;};vector e[maxn * 10];int cnt;struct segement_tree{ int in[maxn << 2],out[maxn << 2]; #define ls i << 1 #define rs i << 1 | 1 void build(int i,int l,int r) { if(l == r) { in[i] = l,out[i] = l; return; } int mid = l + r >> 1; build(ls,l,mid),build(rs,mid + 1,r); in[i] = ++cnt,out[i] = ++cnt; e[in[i]].push_back((node){ in[ls],0}); e[in[i]].push_back((node){ in[rs],0}); e[out[ls]].push_back((node){ out[i],0}); e[out[rs]].push_back((node){ out[i],0}); } void addein(int i,int l,int r,int ql,int qr,int u,int w) { if(l == ql && r == qr) { e[u].push_back((node){ in[i],w}); return; } int mid = l + r >> 1; if(qr <= mid) addein(ls,l,mid,ql,qr,u,w); else if(ql > mid) addein(rs,mid + 1,r,ql,qr,u,w); else addein(ls,l,mid,ql,mid,u,w),addein(rs,mid + 1,r,mid + 1,qr,u,w); } void addeout(int i,int l,int r,int ql,int qr,int u,int w) { if(l == ql && r == qr) { e[out[i]].push_back((node){u,w}); return; } int mid = l + r >> 1; if(qr <= mid) addeout(ls,l,mid,ql,qr,u,w); else if(ql > mid) addeout(rs,mid + 1,r,ql,qr,u,w); else addeout(ls,l,mid,ql,mid,u,w),addeout(rs,mid + 1,r,mid + 1,qr,u,w); }}T;struct pnode{ ll id,dis; bool operator < (const pnode& a) const { return dis > a.dis; }};ll dis[maxn * 10];priority_queue p;int s;void dij(){ memset(dis,0x3f,sizeof(dis)); pnode x; x.dis = 0,x.id = s; dis[s] = 0; p.push(x); while(p.size()) { pnode x = p.top(); p.pop(); int u = x.id; if(dis[u] != x.dis) continue; for(int cur = 0;cur < e[u].size();cur++) { int v = e[u][cur].to,w = e[u][cur].cost; if(dis[v] > dis[u] + w) { dis[v] = dis[u] + w; pnode ne; ne.id = v,ne.dis = dis[v]; p.push(ne); } } }}int main(){ int n = read(),q = read(); s = read(); cnt = n; T.build(1,1,n); for(int i = 1;i <= q;i++) { int op = read(); if(op == 1) { int u = read(),v = read(),w = read(); e[u].push_back((node){v,w}); continue;} int u = read(),l = read(),r = read(),w = read(); if(op == 2) T.addein(1,1,n,l,r,u,w); if(op == 3) T.addeout(1,1,n,l,r,u,w); } dij(); for(int i = 1;i <= n;i++) if(dis[i] == 0x3f3f3f3f3f3f3f3f) printf("-1 "); else printf("%lld ",dis[i]);}