(1) CF786B Legacy
-
有一张 \(n\) 个节点和若干条边。边用 \(q\) 条信息表示：
1 v u w表示有一条连接 \(v \to u\) 的有向边，边权为 \(w\)；2 v l r w表示对于所有 \(u \in [l, r]\)，都有一条连接 \(v \to u\) 的有向边，边权为 \(w\)；3 v l r w表示对于所有 \(u \in [l, r]\)，都有一条连接 \(u \to v\) 的有向边，边权为 \(w\)。
求 \(s\) 到每个点的最短路。
线段树优化建图。
建两颗线段树“入树”和“出树”，每次连边时将入树的线段树节点连向出树的线段树节点。
同时，在入树中，我们连边儿子 \(\to\) 父亲边权为 \(0\)。在出树中连边父亲 \(\to\) 儿子边权为 \(0\)。
又因为两个数中每个叶子节点本质是一样的，所以在相同的叶子节点间连接边权为 \(0\) 的双向边。
最后从某棵树的叶子节点 \(s\) 跑最短路即可。
$\color{blue}\text{Code}$
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1000010;
int n, q, s;
vector<pair<int, int> > g[N];
int root[2];
void add(int a, int b, int w, bool flg = 0) {
g[a].push_back({b, w});
if (flg) add(b, a, w);
return;
}
struct Tree {
int l, r; // 区间
int ls, rs; // 左右儿子
bool flg; // 哪棵树
}tr[N];
int idx;
map<pair<int, bool>, int> Id;
int build(int l, int r, bool flg) {
int u = ++ idx;
tr[u].l = l, tr[u].r = r, tr[u].flg = flg;
if (l != r) {
int mid = l + r >> 1;
tr[u].ls = build(l, mid, flg);
tr[u].rs = build(mid + 1, r, flg);
if (!flg) add(tr[u].ls, u, 0), add(tr[u].rs, u, 0);
else add(u, tr[u].ls, 0), add(u, tr[u].rs, 0);
}
else Id[{l, flg}] = u;
return u;
}
int dis[N];
bool st[N];
void Dijkstra(int s) {
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
q.push({0, s});
memset(dis, 0x3f, sizeof dis);
dis[s] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
if (st[u]) continue;
st[u] = true;
for (auto t : g[u]) {
int v = t.first, w = t.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
return;
}
void u_to_seg(int u, int l, int r, int to, int w) {
if (tr[u].l >= l && tr[u].r <= r) add(to, u, w);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) u_to_seg(tr[u].ls, l, r, to, w);
if (r > mid) u_to_seg(tr[u].rs, l, r, to, w);
}
return;
}
void seg_to_v(int u, int l, int r, int to, int w) {
if (tr[u].l >= l && tr[u].r <= r) add(u, to, w);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) seg_to_v(tr[u].ls, l, r, to, w);
if (r > mid) seg_to_v(tr[u].rs, l, r, to, w);
}
return;
}
signed main() {
cin >> n >> q >> s;
root[0] = build(1, n, 0);
root[1] = build(1, n, 1);
for (int i = 1; i <= n; ++ i ) {
add(Id[{i, 0}], Id[{i, 1}], 0, 1);
}
while (q -- ) {
int op, v, u, l, r, w;
cin >> op;
if (op == 1) {
cin >> v >> u >> w;
add(Id[{v, 0}], Id[{u, 1}], w);
}
else if (op == 2) {
cin >> u >> l >> r >> w;
u_to_seg(root[1], l, r, Id[{u, 0}], w);
}
else {
cin >> v >> l >> r >> w;
seg_to_v(root[0], l, r, Id[{v, 1}], w);
}
}
Dijkstra(Id[{s, 0}]);
for (int i = 1; i <= n; ++ i ) {
int res = dis[Id[{i, 0}]];
if (res > 1e15) res = -1;
cout << res << ' ';
}
return 0;
}
(2) P6348 Journeys
-
有一张 \(n\) 个节点和若干条边。边用 \(m\) 条信息表示：
l1 r1 l2 r2表示对于所有 \(u \in [l1, r1], v \in [l2, r2]\)，都有一条双向边连接 \(u, v\)。
求 \(P\) 到每个点的最短路。
与上题类似。对于每条信息 l1 r1 l2 r2，我们建立一个虚点，并将 \(l1 \sim r_1\) 和 \(l2 \sim r2\) 向这个虚点连接边权为 \(\frac 12\) 的双向边。这里仍然是线段树优化。
然后跑最短路即可。
实际上，在向虚点连边时可以连接边权为 \(1\) 的边，最终答案全部除以二。
$\color{blue}\text{Code}$
#include <bits/stdc++.h>
using namespace std;
const int N = 5000010;
int n, q, s;
vector<pair<int, double> > g[N];
int root[2];
void add(int a, int b, double w) {
g[a].push_back({b, w});
return;
}
struct Tree {
int l, r; // 区间
int ls, rs; // 左右儿子
bool flg; // 哪棵树
}tr[N];
int idx;
map<pair<int, bool>, int> Id;
int build(int l, int r, bool flg) {
int u = ++ idx;
tr[u].l = l, tr[u].r = r, tr[u].flg = flg;
if (l != r) {
int mid = l + r >> 1;
tr[u].ls = build(l, mid, flg);
tr[u].rs = build(mid + 1, r, flg);
if (!flg) add(tr[u].ls, u, 0), add(tr[u].rs, u, 0);
else add(u, tr[u].ls, 0), add(u, tr[u].rs, 0);
}
else Id[{l, flg}] = u;
return u;
}
double dis[N];
bool st[N];
void Dijkstra(int s) {
priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > q;
q.push({0, s});
for (int i = 1; i <= idx; ++ i ) dis[i] = 1e18;
dis[s] = 0;
while (q.size()) {
int u = q.top().second;
q.pop();
if (st[u]) continue;
st[u] = true;
for (auto t : g[u]) {
int v = t.first;
double w = t.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push({dis[v], v});
}
}
}
return;
}
void u_to_seg(int u, int l, int r, int to, double w) {
if (tr[u].l >= l && tr[u].r <= r) add(to, u, w);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) u_to_seg(tr[u].ls, l, r, to, w);
if (r > mid) u_to_seg(tr[u].rs, l, r, to, w);
}
return;
}
void seg_to_v(int u, int l, int r, int to, double w) {
if (tr[u].l >= l && tr[u].r <= r) add(u, to, w);
else {
int mid = tr[u].l + tr[u].r >> 1;
if (l <= mid) seg_to_v(tr[u].ls, l, r, to, w);
if (r > mid) seg_to_v(tr[u].rs, l, r, to, w);
}
return;
}
signed main() {
cin >> n >> q >> s;
root[0] = build(1, n, 0);
root[1] = build(1, n, 1);
for (int i = 1; i <= n; ++ i ) {
add(Id[{i, 0}], Id[{i, 1}], 0);
add(Id[{i, 1}], Id[{i, 0}], 0);
}
while (q -- ) {
int l1, r1, l2, r2;
cin >> l1 >> r1 >> l2 >> r2;
seg_to_v(root[0], l1, r1, ++ idx, 0.5);
u_to_seg(root[1], l2, r2, idx, 0.5);
seg_to_v(root[0], l2, r2, ++ idx, 0.5);
u_to_seg(root[1], l1, r1, idx, 0.5);
}
Dijkstra(Id[{s, 0}]);
for (int i = 1; i <= n; ++ i ) {
cout << dis[Id[{i, 0}]] << '\n';
}
return 0;
}