给出一个带权有向图,有三种操作:
1.u->v 添加一条权值为 w 的边
2. 区间 [l,r]->v 添加权值为 w 的边
3.v->区间 [l,r] 添加权值为 w 的边
求 st 点到每个点的最短路
首先我们思考到,若是每次对于 l,r 区间内的每一个点都执行一次加边操作,不仅耗时还耗空间。
那么我们要想到一个办法去优化它。一看到 lr 区间,我们就会想到线段树对吧。
没错啦这题就是用线段树去优化它。
首先我们建一棵线段树,然后很容易想到,我们只需要把这一棵线段树当做图中的一部分去跑 dijkstra,也可以跑出正确答案。
当然这棵树上的每一条边边权都为 0。
看到 2.3 操作,我们需要建两颗线段树,其中一颗线段树是区间到点,另一个是点到区间。
区间到点的线段树是反着连有向边的,这个简单思考一下便可得出。
建树的时候我们需要对于每一个叶子节点连向对应的单点。
这样一来,因为每个区间最多只会有 $\log n$ 个点,我们只需要最多连 $\log n$ 条边就可以完成一次加边操作。
最后跑 dijkstra 的时候一定要加堆优化,否则会很惨的。。因为边数特别大。。。
当然本题解写的非常之简略,可以去 bilibili[嘿嘿嘿] 搜索 "codeforces div ABC"(好像是这样) 就可以搜索到某大神的直播讲题。
好的接下来是扯淡时间,首先我先在自己学校 oj 上交了一发,然后 a 掉了。于是我就很高兴地开始写本篇题解。写着写着突然想去 cf 上面交一发。。然后直接第七个点就爆炸了。对拍以后发现是自己的 dijkstra 出了问题。
那么现在问题来了,为什么我们的 oj 上可以 ac 呢?
调了数据发现我们 oj 上的数据只有五个点 && 前四个点 n<5。。。。
于是就继续改,对拍了一个中午都没错。。结果发现自己 oj 上拿下来的标程是错的。。
然而这个题目我卡了好久好久好久好久啊。。都快调疯了。
最后发现是 dijkstra 写错了。。。我都想扇死自己了。
最后 A 掉了以后,搞了一发数据,扔到了 oj 上,卡掉了 80% 的 Ac 代码。
还有一个非常需要注意到的地方是,总的边数经过计算可得知为 $6n+q\log n$ 条边,也就是≥2500000。
点数也要开到 5n 级别,也就是≥500000。
加边时间复杂度:$O(q\log n)$
最短路时间复杂度 $O(n\log(q\log n))$
此题的数据生成器:(建议调数据大小的时候要在全程序范围内修改,否则只修改 define 部分会跑出来非法的数据,可不能怪我哟嘿嘿嘿)
- 1#include 2#include 3#include 4#include 5#define maxN 100000 6#define maxQ 100000 7#define maxW 100000000 8#define starT(rand() % 100000 + 1) 9 using namespace std;
- 10 int main() {
- 11 srand((unsigned) time(NULL));
- 12 freopen("cf787d7.in", "w", stdout);
- 13 int n = maxN,
- q = maxQ,
- s = starT;
- 14 printf("%d %d %d\n", n, q, s);
- 15
- for (int i = 1; i <= q; i++) {
- 16 int num = rand() % 11 + 1;
- 17
- if (num == 1) printf("1 %d %d %d\n", rand() % maxN + 1, rand() % maxN + 1, rand() % maxW + 900000000);
- 18
- else if (num < 7) {
- 19 int l = rand() % 10000 + 1;
- 20 printf("2 %d %d %d %d\n", rand() % maxN + 1, l, l + 30000 + rand() % (60000) + 1, rand() % maxW + 900000000);
- 21
- } else {
- 22 int l = rand() % 10000 + 1;
- 23 printf("3 %d %d %d %d\n", rand() % maxN + 1, l, l + 30000 + rand() % (60000) + 1, rand() % maxW + 900000000);
- 24
- }
- 25
- }
- 26
- }
- 1#include 2#include 3#include 4#include 5#include 6#include 7 using namespace std;
- 8 int n,
- eq,
- s,
- u,
- v,
- l,
- r,
- Tsk,
- nodetot,
- now,
- tot = 0;
- 9 priority_queue < pair < long long,
- int > >q;
- 10 struct node {
- 11 int to,
- next,
- w;
- 12
- }
- e[7000070];
- 13 bool vis[700050];
- 14 int h[700050],
- lch[700040],
- w;
- 15 long long dist[700050];
- 16 void add(int u, int v, int w) {
- 17 e[++tot].to = v;
- e[tot].next = h[u];
- h[u] = tot;
- e[tot].w = w;
- 18
- }
- 19 int read() {
- 20 int x = 0,
- f = 1;
- 21 char c = getchar();
- 22
- for (; ! isdigit(c); c = getchar()) if (c == '-') f = -1;
- 23
- for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
- 24
- return x * f;
- 25
- }
- 26 void addTree(int v, int l, int r, long long w, int nl, int nr, int now) {
- 27
- if (nl >= l && nr <= r) add(v, now, w);
- 28
- else {
- 29 int mid = (nl + nr) >> 1;
- 30
- if (r <= mid) addTree(v, l, r, w, nl, mid, lch[now - n]);
- 31
- else if (l > mid) addTree(v, l, r, w, mid + 1, nr, lch[now - n] + 1);
- 32
- else {
- 33 addTree(v, l, mid, w, nl, mid, lch[now - n]);
- 34 addTree(v, mid + 1, r, w, mid + 1, nr, lch[now - n] + 1);
- 35
- }
- 36
- }
- 37
- }
- 38 void Treeadd(int v, int l, int r, long long w, int nl, int nr, int now) {
- 39
- if (nl >= l && nr <= r) add(now, v, w);
- 40
- else {
- 41 int mid = (nl + nr) >> 1;
- 42
- if (r <= mid) Treeadd(v, l, r, w, nl, mid, lch[now - n]);
- 43
- else if (l > mid) Treeadd(v, l, r, w, mid + 1, nr, lch[now - n] + 1);
- 44
- else {
- 45 Treeadd(v, l, mid, w, nl, mid, lch[now - n]);
- 46 Treeadd(v, mid + 1, r, w, mid + 1, nr, lch[now - n] + 1);
- 47
- }
- 48
- }
- 49
- }
- 50 void buildTreest(int now, int l, int r) {
- 51
- if (l == r) {
- 52 add(now, l, 0);
- 53
- return;
- 54
- };
- 55 int mid = (l + r) >> 1;
- 56 add(now, ++nodetot, 0);
- 57 lch[now - n] = nodetot;
- 58 add(now, ++nodetot, 0);
- 59 buildTreest(lch[now - n], l, mid);
- 60 buildTreest(lch[now - n] + 1, mid + 1, r);
- 61
- }
- 62 void buildTreeet(int now, int l, int r) {
- 63
- if (l == r) {
- 64 add(l, now, 0);
- 65
- return;
- 66
- };
- 67 int mid = (l + r) >> 1;
- 68 add(++nodetot, now, 0);
- 69 lch[now - n] = nodetot;
- 70 add(++nodetot, now, 0);
- 71 buildTreeet(lch[now - n], l, mid);
- 72 buildTreeet(lch[now - n] + 1, mid + 1, r);
- 73
- }
- 74 void Dijkstra(int st) {
- 75 dist[st] = 0;
- 76 now = st;
- 77 q.push(make_pair(0, st));
- 78
- while (!q.empty()) {
- 79 vis[now] = 1;
- 80 pair < long long,
- int > x = q.top();
- 81 q.pop();
- 82 now = x.second;
- 83
- for (int i = h[now];~i; i = e[i].next) {
- 84
- if (dist[e[i].to] > dist[now] + e[i].w) {
- 85 dist[e[i].to] = dist[now] + e[i].w;
- 86 q.push(make_pair( - dist[e[i].to], e[i].to));
- 87
- }
- 88
- }
- 89
- }
- 90
- }
- 91 int main() {
- 92 memset(h, -1, sizeof(h));
- 93 memset(dist, 0x7f, sizeof(dist));
- 94 n = read();
- 95 eq = read();
- 96 s = read();
- 97 nodetot = n + 1;
- 98 buildTreest(n + 1, 1, n);
- 99 buildTreeet(++nodetot, 1, n);
- 100
- for (int i = 1; i <= eq; i++) {
- 101 Tsk = read();
- 102
- if (Tsk == 1) {
- 103 v = read();
- 104 u = read();
- 105 w = read();
- 106 add(v, u, w);
- 107
- } else if (Tsk == 2) {
- 108 v = read();
- 109 l = read();
- 110 r = read();
- 111 w = read();
- 112 addTree(v, l, r, w, 1, n, n + 1);
- 113
- } else {
- 114 v = read();
- 115 l = read();
- 116 r = read();
- 117 w = read();
- 118 Treeadd(v, l, r, w, 1, n, n * 3);
- 119
- }
- 120
- }
- 121 Dijkstra(s);
- 122
- for (int i = 1; i <= n - 1; i++) printf("%lld ", (dist[i] == 0x7f7f7f7f7f7f7f7f) ? -1 : dist[i]);
- 123 printf("%lld\n", (dist[n] == 0x7f7f7f7f7f7f7f7f) ? -1 : dist[n]);
- 124
- }
来源: http://www.cnblogs.com/skylynf/p/7172074.html