CF786 B Legacy

CF786 B Legacy

CF786 B Legacy

题意

有$n$个点,有$q$次操作,以$s$为起点

三种操作:

  1. 将点$i$连向点$j$,附带权值$w$
  2. 将点$v$连向区间$[l,r]$中的所有点,权值都是$w$
  3. 将区间$[l,r]$中所有点都连向点$v$,权值都是$w$

最后问:以$s$为起点,到$1$~$n$所有点的最短路

思路

暴力建边肯定是要爆炸的

那我们考虑用线段树,怎么用呢,就是用线段树上的某个结点来代替区间$[l,r]$

线段树基础:线段树基础

线段树建模上跑最短路:参考博客

题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = 1e18 + 5;
const int mod = 1e8;
const int Max = 1e5 + 10;

struct Node
{
int l, r;
int num;
} node1[Max << 3], node2[Max << 3]; //记录上下两个线段树

struct Edge
{
int to;
ll dis;
};

vector<Edge> edge[Max << 3]; //记录边的信息
int pos1[Max << 3], pos2[Max << 3]; //记录上下两个树中的每个叶子结点在线段树中的下标
int n, q, s;
int tot;

void build_up(int l, int r, int num) //自底向上建边,下线段树
{
node1[num].l = l;
node1[num].r = r;
node1[num].num = ++tot; //每一个顶点都有唯一的编号,便于建边
if (l == r)
{
pos1[l] = node1[num].num; //记录下线段树的叶子结点对应的编号,借助pos1直接找到叶子结点
return;
}
int mid = (l + r) >> 1;
build_up(l, mid, num << 1);
build_up(mid + 1, r, num << 1 | 1);

edge[node1[num << 1].num].push_back({node1[num].num, 0});
edge[node1[num << 1 | 1].num].push_back({node1[num].num, 0}); //子结点向父结点建边
}

void build_down(int l, int r, int num) //自顶向下建边
{
node2[num].l = l;
node2[num].r = r;
node2[num].num = ++tot;
if (l == r)
{
pos2[l] = node2[num].num;
//记录上线段树的叶子结点对应的编号,借助pos1直接找到叶子结点
edge[node2[num].num].push_back({pos1[l], 0});
//由上线段树的叶子结点向下线段树的叶子结点建边
return;
}
int mid = (l + r) >> 1;
build_down(l, mid, num << 1);
build_down(mid + 1, r, num << 1 | 1);
edge[node2[num].num].push_back({node2[num << 1].num, 0});
edge[node2[num].num].push_back({node2[num << 1 | 1].num, 0}); //父结点向子结点建边
}

//由区间向点建边
void upData_section_to_dot(int l, int r, int v, ll dis, int num)
{
if (l <= node1[num].l && node1[num].r <= r)
{
edge[node1[num].num].push_back({pos2[v], dis});
//由下线段树的区间向上线段树的叶子结点建边
return;
}
int mid = (node1[num].l + node1[num].r) >> 1;
if (l <= mid)
upData_section_to_dot(l, r, v, dis, num << 1);
if (r > mid)
upData_section_to_dot(l, r, v, dis, num << 1 | 1);
}

//由点向边建边
void upData_dot_to_section(int l, int r, int u, ll dis, int num)
{
if (l <= node2[num].l && node2[num].r <= r)
{
edge[pos1[u]].push_back({node2[num].num, dis});
//由下线段树的点向上线段树的区间建边
return;
}
int mid = (node2[num].l + node2[num].r) >> 1;
if (l <= mid)
upData_dot_to_section(l, r, u, dis, num << 1);
if (r > mid)
upData_dot_to_section(l, r, u, dis, num << 1 | 1);
}

bool vis[Max << 3]; //访问状态
ll dist[Max << 3]; //各个点到起点的距离

void dijkstra(int start)
{
memset(vis, 0, sizeof(vis)); //初始化访问状态
for (int i = 1; i <= 8 * n; i++) //初始化各个点到起点的距离
dist[i] = inf;
dist[start] = 0;
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> queues; //以到起点距离单增的优先队列
queues.push({0, start}); //起点入队

while (!queues.empty())
{
int u = queues.top().second;
queues.pop();
if (vis[u])
continue; //重复访问
vis[u] = true;
for (int i = 0; i < edge[u].size(); i++)
{
int v = edge[u][i].to;
ll dis = edge[u][i].dis;
if (vis[v])
continue; //重复访问
if (dist[v] > dist[u] + dis) //缩边
{
dist[v] = dist[u] + dis;
queues.push({dist[v], v});
}
}
}
for (int i = 1; i <= n; i++) //输出结果
{
if (dist[pos1[i]] != inf)
printf("%lld ", dist[pos1[i]]);
else
printf("-1 ");
}
printf("\n");
}

int main()
{
while (scanf("%d%d%d", &n, &q, &s) != EOF)
{
for (int i = 0; i < Max << 3; i++) //多组输入的初始化
edge[i].clear();
tot = 0; //控制编号的变量
build_up(1, n, 1);
build_down(1, n, 1); //构建上下线段树
while (q--)
{
int type, u, v, l, r;
ll cost;
scanf("%d", &type);
if (type == 1)
{
scanf("%d%d%lld", &u, &v, &cost);
edge[pos1[u]].push_back({pos2[v], cost});
//由下线段树的叶子结点向上线段树的叶子结点建边
}
else if (type == 2)
{
scanf("%d%d%d%lld", &u, &l, &r, &cost);
upData_dot_to_section(l, r, u, cost, 1);
//由下线段树的叶子结点向上线段树的区间结点建边
}
else
{
scanf("%d%d%d%lld", &v, &l, &r, &cost);
upData_section_to_dot(l, r, v, cost, 1);
//由下线段树的区间结点向上线段树的叶子结点建边
}
}
dijkstra(pos1[s]);
}
return 0;
}