有$n$个点，$q$次3种类型的操作：
$1\ u\ v\ w$，连边$u\to v$，权值为$w$；
$2\ v\ l\ r\ w$，连边$v\to [l, r]$，权值为$w$；
$3\ v\ l\ r\ w$，连边$[l,r]\to v$，权值为$w$。
其中$[l,r]$表示结点编号在此范围内的所有结点。
求给定的源点$s$到达点$u(1\leq u \leq n)$的最短路长度。
如果暴力建边的话，最坏情况会有$q\times n$条边。
对于区间操作，考虑线段树优化建边。
原$n$个点仍然保留，作为线段树的叶子结点。假如连边$(v\to [l,r],w)$，那么$v$向线段树中代表$[l,r]$的结点连权值为$w$的边，但只是这样连上去了回不到$n$个叶子结点上，所以每个点要向其左右儿子连权值为0的边。
因为这棵线段树中代表$[l,r]$的结点向叶子结点的路径长度已经为0，所以对于第三种操作$([l,r]\to v, w)$，需要建另外一棵线段树，代表$[l,r]$的结点向$v$连权值为$w$的边，每个点向父亲结点连权值为0的边。
线段树结点从$n+1$开始编号，叶子结点直接用$1\sim n$编号很方便，对于操作1可以直接连边。
用优先队列优化的Dijkstra算法求单源最短路，最终时间复杂度为$O(qlog^2n)$。
#include <cstdio> #include <cstring> #include <queue> #include <utility> #define lson son[rt][0] #define rson son[rt][1] typedef long long LL; typedef std::pair<LL, int> P; const LL INF=0x3f3f3f3f3f3f3f3fll; const int N = 100010 << 3, M = 5000010; struct Edge { int to, nex, w; } edge[M]; int head[N], cnt_e, tot; int son[N][2]; LL dis[N]; void init() { memset(head, 0, sizeof(head)); cnt_e = 0; } void add_edge(int u, int v, int val) { edge[++cnt_e].to = v; edge[cnt_e].w = val; edge[cnt_e].nex = head[u]; head[u] = cnt_e; } void build(int &rt, int L, int R, int tp) { if (L == R) { rt = L; return ; } rt = ++tot; int mid = (L + R) >> 1; build(lson, L, mid, tp); build(rson, mid + 1, R, tp); if (tp == 2) { add_edge(rt, lson, 0); add_edge(rt, rson, 0); } else { add_edge(lson, rt, 0); add_edge(rson, rt, 0); } } void modify(int l, int r, int L, int R, int rt, int u, int w, int tp) { if (L >= l && R <= r) { tp == 2 ? add_edge(u, rt, w) : add_edge(rt, u, w); return ; } int mid = (L + R) >> 1; if (l <= mid) modify(l, r, L, mid, lson, u, w, tp); if (r > mid) modify(l, r, mid + 1, R, rson, u, w, tp); } void dijkstra(int s) { std::priority_queue<P, std::vector<P>, std::greater<P> > que; memset(dis, 0x3f, sizeof(dis)); dis[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (p.first > dis[v]) continue; for (int i = head[v], u; i; i = edge[i].nex) { u = edge[i].to; if (dis[v] + edge[i].w < dis[u]) { dis[u] = dis[v] + edge[i].w; que.push(P(dis[u], u)); } } } } int main() { int n, q, s; while (~scanf("%d %d %d", &n, &q, &s)) { init(); int rt2, rt3; tot = n; build(rt2, 1, n, 2); build(rt3, 1, n, 3); int tp, u, v, l, r, w; while (q--) { scanf("%d", &tp); if (tp == 1) { scanf("%d %d %d", &u, &v, &w); add_edge(u, v, w); } else { scanf("%d %d %d %d", &v, &l, &r, &w); modify(l, r, 1, n, (tp == 2 ? rt2 : rt3), v, w, tp); } } dijkstra(s); for (int i = 1; i <= n; i++) printf("%I64d%c", (dis[i] == INF ? -1ll : dis[i]), " \n"[i==n]); } return 0; }
CodeForces-786B Legacy (线段树优化建图，单源最短路)
原文：https://www.cnblogs.com/kangkang-/p/11386349.html
