第一次写线段树优化建边。
根据本题的要求，我们可以建两棵线段树，然后在建$n$个点，然后把第一棵线段树上每一个点$(p, l, r)$（结点编号为$p$, 表示区间是$[l, r]$），连边$\forall i \in [l, r]\ (i, p, 0)$，与之相对，把第二棵线段树上的点$(p, l, r)$连边$\forall i \in [l, r]\ (p, i, 0)$。
根据本题的特殊的连边条件限制，我们把一个区间拆成线段树上的$log$个点，然后在对应的点上连一下即可。
跑一遍最短路即可。
注意点数是$n + 2nlogn$，边数上限是$2nlogn + mlogn$，数组要开够。
时间复杂度$O(nlogn)$。
Code：
#include <cstdio> #include <cstring> #include <queue> #include <iostream> #include <vector> using namespace std; typedef long long ll; typedef pair <ll, int> pin; const int N = 1e5 + 5; const int M = 1.2e7 + 5; const ll inf = 0x3f3f3f3f3f3f3f3f; int n, m, tot = 0, head[N << 4]; ll dis[N << 4]; bool vis[N << 4]; vector <int> vec; struct Edge { int to, nxt; ll val; } e[M]; inline void add(int from, int to, ll val) { e[++tot].to = to; e[tot].val = val; e[tot].nxt = head[from]; head[from] = tot; } template <typename T> inline void read(T &X) { X = 0; char ch = 0; T op = 1; for(; ch > '9'|| ch < '0'; ch = getchar()) if(ch == '-') op = -1; for(; ch >= '0' && ch <= '9'; ch = getchar()) X = (X << 3) + (X << 1) + ch - 48; X *= op; } namespace SegT { struct Node { int lc, rc; } s[N << 4]; int root[2], nodeCnt; #define lc(p) s[p].lc #define rc(p) s[p].rc #define mid ((l + r) >> 1) void build(int &p, int l, int r, int type) { p = ++nodeCnt; for(int i = l; i <= r; i++) if(!type) add(i, p, 0LL); else add(p, i, 0LL); if(l == r) return; build(lc(p), l, mid, type); build(rc(p), mid + 1, r, type); } void getRan(int p, int l, int r, int x, int y) { if(x <= l && y >= r) { vec.push_back(p); return; } if(x <= mid) getRan(lc(p), l, mid, x, y); if(y > mid) getRan(rc(p), mid + 1, r, x, y); } } using namespace SegT; priority_queue <pin> Q; inline void dij(int st) { memset(dis, 0x3f, sizeof(dis)); Q.push(pin(dis[st] = 0LL, st)); for(; !Q.empty(); ) { int x = Q.top().second; Q.pop(); if(vis[x]) continue; vis[x] = 1; for(int i = head[x]; i; i = e[i].nxt) { int y = e[i].to; if(dis[y] > dis[x] + e[i].val) { dis[y] = dis[x] + e[i].val; Q.push(pin(-dis[y], y)); } } } } int main() { read(n), read(m); int st; read(st); nodeCnt = n; build(root[0], 1, n, 0), build(root[1], 1, n, 1); for(int op, i = 1; i <= m; i++) { read(op); if(op == 1) { int x, y; ll v; read(x), read(y), read(v); add(x, y, v); } if(op == 2) { int x, l, r; ll v; read(x), read(l), read(r), read(v); vec.clear(); getRan(root[1], 1, n, l, r); int vecSiz = vec.size(); for(int j = 0; j < vecSiz; j++) { int y = vec[j]; add(x, y, v); } } if(op == 3) { int y, l, r; ll v; read(y), read(l), read(r), read(v); vec.clear(); getRan(root[0], 1, n, l, r); int vecSiz = vec.size(); for(int j = 0; j < vecSiz; j++) { int x = vec[j]; add(x, y, v); } } } dij(st); for(int i = 1; i <= n; i++) printf("%lld ", dis[i] == inf ? -1 : dis[i]); printf("\n"); return 0; }