大致题意：给一个图，有3种边，t=1时，是点u对点v的单向边，t=2时，是点u到标号为[l,r]的点的单向边，t=3时，是标号为[l,r]到点u的边，求单源多汇最短路。
注意，点的数量为10^5，所以如果把每个点之间的边都存下来会占用GB级别的内存，显然这不是出题者所希望看到的，我们应该对存储边的方式进行调整。
既然我们不能把每个点对点的边都存下来，不如新建一些集散点用进行集中和分散，就像现实生活中的货运集散点一样，这样的话边的数量就会有所减少。
再观察题目给出边的特点，它虽然给出的边是一个点指向多个点的边，但是这些点的边都标号都是连续的。所以把标号相邻的点联向一个共同的集散点，然后将二者共同的边改为从这个集散点联向其他点，这样将会稳定且有效地减少边的数量。
但是对于新图，边数仍然不少，但我们仍然可以对新建的点重复上述步骤来增加集散点，直到所有点都联向了一个集散点。
注意，入边和出边的集散点应该分开来建。
在纸上模拟上述步骤，会发现这不就是两颗线段树吗？对，它的确和线段树相差无几。所以我们可以用线段树的建树函数和更新过程来进行构建新图。之于最短路就不是本题的主要问题了。
#include <bits/stdc++.h> #define maxn 1700000 #define ll long long #define mp make_pair #define pb push_back #define st first #define ed second using namespace std; inline void read(int &x) { char ch; bool flag = false; for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true; for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar()); x = flag ? -x : x; } inline void write(int x) { static const int maxlen = 100; static char s[maxlen]; if (x < 0) { putchar('-'); x = -x;} if (!x) { putchar('0'); return; } int len = 0; for (; x; x /= 10) s[len++] = x % 10 + '0'; for (int i = len - 1; i >= 0; --i) putchar(s[i]); } set< pair<ll, int> > s; vector < pair<int, int> > v[maxn]; int n, m, st; ll dist[maxn]; int num[maxn][2], tot; //x=0代表入点，x=1代表出点 int build(int p, int l, int r, int x) { if (l == r) return num[p][x] = l; num[p][x] = ++tot; int mid = (l + r) / 2; int ls = build(p * 2, l, mid, x); int rs = build(p * 2 + 1, mid + 1, r, x); if (x == 0) { v[num[p][x]].push_back(mp(ls, 0)); v[num[p][x]].push_back(mp(rs, 0)); } else { v[ls].push_back(mp(num[p][x], 0)); v[rs].push_back(mp(num[p][x], 0)); } return num[p][x]; } void update(int p, int l, int r, int a, int b, int x, int y, int op) { if ((l == a) && (r == b)) { if (op == 0) v[x].push_back(mp(num[p][op], y)); else v[num[p][op]].push_back(mp(x, y)); return ; } int mid = (l + r) / 2; if (b <= mid) update(p * 2, l, mid, a, b, x, y, op); else if (a > mid) update(p * 2 + 1, mid + 1, r, a, b, x, y, op); else { update(p * 2, l, mid, a, mid, x, y, op); update(p * 2 + 1, mid + 1, r, mid + 1, b, x, y, op); } } int main() { memset(dist, -1, sizeof(dist)); read(n); read(m); read(st); tot = n; build(1, 1, n, 0); build(1, 1, n, 1); for (int i = 1; i <= m; i++) { int t; read(t); if (t == 1) { int a, b, c; read(a); read(b); read(c); v[a].pb(make_pair(b, c)); } else { int v, l, r, w; scanf("%d%d%d%d", &v, &l, &r, &w); update(1, 1, n, l, r, v, w, t - 2); } } s.insert(mp(0, st)); while (!s.empty()) { ll y = s.begin()->st, x = s.begin()->ed; s.erase(s.begin()); if (dist[x] != -1) continue; dist[x] = y; for (int i = 0; i < v[x].size(); i++) if (dist[v[x][i].st] == -1) s.insert(mp(1ll * v[x][i].ed + dist[x], v[x][i].st)); } for (int i = 1; i <= n; i++) printf("%I64d ", dist[i]); return 0; }
